AT_awc0002_e お菓子の詰め合わせ

高橋君は駄菓子屋で $ N $ 種類のお菓子を見つけました。 $ i $ 番目 $ (1 \leq i \leq N) $ のお菓子の値段は $ A_i $ 円です。各お菓子は $ 1 $ つずつしか在庫がないため、それぞれのお菓子について「買う」か「買わない」かのどちらかを選びます。なお、異なる種類のお菓子であっても値段が同じことがありますが、それらは異なるお菓子として区別します。 高橋君はちょうど $ S $ 円を持っています。せっかくなので、手持ちのお金を余らせず、ぴったり $ S $ 円分のお菓子を買いたいと考えています。 $ N $ 種類のお菓子から $ 0 $ 個以上を選ぶ方法のうち、選んだお菓子の値段の合計がちょうど $ S $ 円になるような選び方は何通りあるか求めてください。ただし、 $ 1 $ つもお菓子を選ばない場合、値段の合計は $ 0 $ 円とみなします。

> $ N $ $ S $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ - $ 1 $ 行目には、お菓子の種類数を表す整数 $ N $ と、高橋君の所持金を表す整数 $ S $ が、スペース区切りで与えられる。 - $ 2 $ 行目には、各お菓子の値段を表す整数 $ A_1, A_2, \ldots, A_N $ が、スペース区切りで与えられる。

選んだお菓子の値段の合計がちょうど $ S $ 円になるような選び方の個数を $ 1 $ 行で出力してください。

### Constraints - $ 1 \leq N \leq 40 $ - $ 0 \leq S \leq 10^{12} $ - $ 1 \leq A_i \leq 10^{12} $ - 入力はすべて整数