题目描述

有 $N$ 个袋子里装着饼干。第 $i$ 个袋子里有 $A_i$ 个饼干。

Takaki 将选择一些袋子，并吃掉里面的所有饼干。在这里，也可以选择全部或者不选择袋子。

他想要选择袋子，使得里面的饼干的总数模 $2$ 和为 $P$。有多少种选择袋子的方式？

约束条件

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

输入

输入从标准输入读取，格式如下：

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

输出

打印选择袋子的方式的数量，使得里面的饼干的总数模 $2$ 和为 $P$。

示例输入 1

2 0
1 3

示例输出 1

2

有两种选择袋子的方式，使得里面的饼干的总数模 $2$ 和为 $0$：

• 不选择任何袋子。饼干的总数为 $0$。
• 选择两个袋子。饼干的总数为 $4$。

示例输入 2

1 1
50

示例输出 2

0

示例输入 3

3 0
1 1 1

示例输出 3

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

示例输出 4

17592186044416