题目描述

いくつかのビスケットの入った袋が $N$ 個あります．$i$ 番目の袋には $A_i$ 個のビスケットが入っています．

高木君は，このうちいくつかの袋を選んで，選んだ袋に入っているビスケットをすべて食べるということを行います． このとき，袋を一つも選ばなかったり，すべての袋を選んだりしてもかまいません．

高木君は，食べるビスケットの枚数を $2$ で割ると余りが $P$ に等しくなるようにしたいです． このような袋の選び方は何通りあるか求めてください．

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

高木君が食べるビスケットの枚数を $2$ で割ると $P$ に等しくなるような，袋の選び方は何通りあるかを出力せよ．

题目大意

有n包饼干，第i包里有A_i个饼干，你将会选择一些包饼干然后将所有你选择的包里面的饼干吃掉（当然你也可以一包也不选），你想要选择一些包饼干使得包里面饼干的总数在模2意义下与P同余，问有多少种方法？

2 0
1 3

2

1 1
50

0

3 0
1 1 1

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$

Sample Explanation 1

食べるビスケットの枚数が $2$ で割って $0$ に等しくなるような選び方は $2$ 通りです： - どちらの袋も選ばない．食べるビスケットの枚数は $0$ である． - どちらの袋も選ぶ．食べるビスケットの枚数は $4$ である．

Sample Explanation 3

同じ枚数のビスケットが入っている場合でも，異なる袋は区別します．