Code Submission Evaluation System Login

CSES Problem Set

Meet in the Middle


Task | Statistics


CSES - Meet in the MiddleCSES - Meet in the Middle

Time limit:1.00 s Memory limit:512 MB

You are given an array of $n$ numbers. In how many ways can you choose a subset of the numbers with sum $x$?

Input

The first input line has two numbers $n$ and $x$: the array size and the required sum.

The second line has $n$ integers $t_1,t_2,\dots,t_n$: the numbers in the array.

Output

Print the number of ways you can create the sum $x$.

Constraints
Example

Input:
4 5
1 2 3 2


Output:
3