配点 : $200$ 点

問題文

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

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

高木君は，食べるビスケットの枚数を $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$ に等しくなるような，袋の選び方は何通りあるかを出力せよ．

2 0
1 3

2

食べるビスケットの枚数が $2$ で割って $0$ に等しくなるような選び方は $2$ 通りです：

• どちらの袋も選ばない．食べるビスケットの枚数は $0$ である．
• どちらの袋も選ぶ．食べるビスケットの枚数は $4$ である．

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