AT_awc0002_e お菓子の詰め合わせ

Takahashi found $ N $ kinds of sweets at a candy shop. The price of the $ i $ -th $ (1 \leq i \leq N) $ sweet is $ A_i $ yen. Since there is only one of each sweet in stock, for each sweet he must choose either "buy" or "don't buy." Note that different kinds of sweets may have the same price, but they are still distinguished as different sweets. Takahashi has exactly $ S $ yen. Since he wants to make the most of it, he would like to buy sweets that cost exactly $ S $ yen in total, without leaving any money. Among all ways to select $ 0 $ or more sweets from the $ N $ kinds, find the number of ways such that the total price of the selected sweets is exactly $ S $ yen. Note that if no sweets are selected, the total price is considered to be $ 0 $ yen.

> $ N $ $ S $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ - The first line contains an integer $ N $ representing the number of kinds of sweets and an integer $ S $ representing the amount of money Takahashi has, separated by a space. - The second line contains integers $ A_1, A_2, \ldots, A_N $ representing the price of each sweet, separated by spaces.

Print in one line the number of ways to select sweets such that the total price of the selected sweets is exactly $ S $ yen.

### Constraints - $ 1 \leq N \leq 40 $ - $ 0 \leq S \leq 10^{12} $ - $ 1 \leq A_i \leq 10^{12} $ - All inputs are integers