Meet in the Middle

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 line has two numbers $n(1\le n\le 40)$ and $x(1\le x\le 10^9)$: the array size and the required sum.

The second line has $n$ integers $t_1,t_2,...,t_n(1\le t_i\le 10^9)$: the numbers in the array.

Output

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

Examples