Background

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."

Problem Description

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.

Input Format

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 Format

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).

4 4
1 1 2 2

3

Hint

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

Translated by ChatGPT 5