#12911Subset sum

Given a set s of integers, your task is to determine how many different non-empty subsets sum up to a target value.

Input

The input consists of several test cases. The first line of each test case is a line containing two integers N and T , the number of items of the original set of integers and the target value. After that comes one line with the N integers s_i that belong to the original set s.

• 1 ≤ N ≤ 40
• −10^9 ≤ T, s_i ≤ 10^9

Output

For each test case print on a single line an integer indicating the number of different non-empty subsets that sum up to the target value T . Explication:

On the first test case the target is 0 and the following are the valid subsets: (2, 4, -1, -5), (2, 6, -5, -3), (4, -1, -3), (6, -5, -1).

On the second test case the target is again 0, the only valid subset is: (-3, -2, 5)

6 0
-1 2 -3 4 -5 6
5 0
-7 -3 -2 5 8

4
1