题目描述

有 $N$ 袋饼干。第 $i$ 袋中有 $A_i$ 块饼干。

高木君可以从中选择若干袋，将选中的袋中的所有饼干都吃掉。这里可以一个袋子都不选，也可以选所有的袋子。

高木君希望吃掉的饼干总数除以 $2$ 的余数等于 $P$。请你计算有多少种选袋的方法满足这一条件。

输入格式

输入按以下格式从标准输入读入。

$N$ $P$ $A_1$ $A_2$ ... $A_N$

输出格式

输出满足吃掉的饼干总数除以 $2$ 的余数等于 $P$ 的选袋方法总数。

样例 1

输入

2 0
1 3

输出

2

样例 2

输入

1 1
50

输出

0

样例 3

输入

3 0
1 1 1

输出

4

样例 4

输入

45 1
17 55 85 55 74 20 90 67 40 70 39 89 91 50 16 24 14 43 24 66 25 9 89 71 41 16 53 13 61 15 85 72 62 67 42 26 36 66 4 87 59 91 4 25 26

输出

17592186044416

说明/提示

限制条件

• $1 \leq N \leq 50$
• $P = 0, 1$
• $1 \leq A_i \leq 100$

样例解释 1

使吃掉的饼干总数除以 $2$ 余 $0$ 的选袋方法有 $2$ 种：

• 两个袋子都不选。吃掉的饼干总数为 $0$。
• 两个袋子都选。吃掉的饼干总数为 $4$。

样例解释 3

即便装有相同数量饼干的袋子，不同袋也视为不同。

由 ChatGPT 5 翻译