P1164 Xiao A Orders Dishes

After the ace uim got uoi’s ra (lei medal), he immediately dragged his buddy Xiao A to a... restaurant, the really low-end kind. Pointing at the price list on the wall (too low-end to have a menu), he said, "Order whatever you like."

However, because uim bought some books, he has only $M$ yuan left $(0 < M \le 10000)$. Although the restaurant is low-end, it still has $N$ kinds of dishes $(1 \le N \le 100)$. The $i$-th dish costs $a_i$ yuan $(0 < a_i \le 1000)$. Since it is a very low-end restaurant, there is only one portion of each dish. Xiao A follows the rule of “not stopping until all the money is spent,” so he will order in such a way that the total cost is exactly all the money uim has. He wants to know how many different ways to order. Because Xiao A is too hungry, he can wait at most $1$ second.

The first line contains two integers $N$ and $M$, representing the number of dishes and the amount of money uim has. The second line contains $N$ positive integers $a_i$ (possibly with duplicates), separated by spaces, representing the price of each dish.

Output a single positive integer, the number of ordering plans. It is guaranteed that the answer is in the range $[0, 2^{31}-1]$ (does not exceed the C/C++ int range).

2020.8.29, added a set of hack testdata by @yummy. Translated by ChatGPT 5