問題文

あなたはショッピングモールにあるEVENという店で買い物をします。

名前の通り、その店のすべての商品の値段は $2$ で割り切れます。

その店には $N$ 個の異なる商品があり、各商品の値段は $a_i(1\le i\le N)$ 円です。

あなたは好きな数(0でもよい)の商品の値段を一度だけ半額にできます。

これらの商品から $1$ つ以上の適当な数の商品を選んだ時、値段の合計が $W$ 円になる商品の選び方は何通りあるでしょうか。

入力

$NW$
$a_1\dots a_N$

• 1行目に、 $N$ と $W$ が空白区切りで与えられる。

• 2行目に、 $a_1\dots a_N$ が空白区切りで与えられる。

制約

• $1\le N\le 13$

• $0\le W\le {10}^9$

• $0\le a_i\le {10}^9$

• $a_i$ は $2$ で割り切れる

• 入力は全て整数である

出力

答えを出力してください。

最後に改行してください。

サンプル

3 20
40 10 20

3

5 3
2 2 2 2 2

20