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

$1 \le n \le 40$

$1 \le x \le 10^9$

$1 \le t_i \le 10^9$

Example

Input

4 5
1 2 3 2

Output

3