G :: Subset Sum

Time Limit: 10 Seconds    Memory Limit: 131072 KB

For a given set X of n not-necessarily-distinct numbers and a given number t, the goal is to compute the number of non-empty subsets Y of X with the properties that the sum over all members of Y is at most t and adding any member in X-Y to Y makes the summation greater than t.

Note that the numbers in the set may have the same values, but they must be considered inherently different.

Input

There are multiple test cases in the input. Each test case starts with a line containing two non-negative integers 0≤n≤30 and 0≤t≤1000. The remainder of each test case consists of one or more lines containing n non-negative numbers belonging to X. The input terminates with “0 0” which should not be processed.

Output

For each test case, output the number of subsets defined above.

Sample Input

6 25 
8 9 8 7 16 5 
30 250 
1 2 3 4 5 6 7 8 9 10 11 
12 13 14 15 16 17 18 19 20 
21 22 23 24 25 26 27 28 29 30
0 0 

Sample Output

15 
16509438 

Submit

Source: 11th Iran Nationwide Internet Contest