ぴったり卵を生産 - その 2（paizaランク S 相当）

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

ニワトリが n 羽います。各々のニワトリは a_i 個 (1 ≦ i ≦ n)卵を産みます。それぞれのニワトリを自由に選択し、（この場合選び方は全部で 2 ^ n 通りあります。）選んだニワトリが産む卵の総和が k 個になる選び方は何通りあるか求めてください。

入力される値

n k
a_1 ... a_n

・ 1 行目に n, k がそれぞれ整数で半角スペース区切りで与えられます。
・ 2 行目にそれぞれのニワトリが産む卵の個数 a_i (1 ≦ i ≦ n)が整数で半角スペース区切りで与えられます。

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

条件: すべてのテストケースにおいて、以下の条件をみたします。

・ 2 ≦ n ≦ 30
・ 0 ≦ k ≦ 3000000000
・ 0 ≦ a_i ≦ 100000000