My Friends Are Small

Time limit8sMemory limit512 MB

Summary

Count subsets of friend weights that can be the final backpack load when items are added one by one in any order until no further friend fits under weight limit W.

Level: Hard8 of 10
Topics: Dynamic programming, Sorting, Combinatorics, Greedy
Solved: No attempts yet

Problem

I have a great many friends. Every one of them is very small.

I often go out with my friends. I put several friends in my backpack and go out with them.

Every morning I decide which friends I will go out with that day. I put the friends into the empty backpack one at a time.

I am not very strong. So there is a limit to the weight of friends I can carry at once.

I put friends in without exceeding the weight limit. The order I put them in depends on my mood.

As long as there are still friends I can put in, I do not stop putting them in. I never stop.

... By the way, how many combinations of friends can end up in the backpack in total?

Input

N W
w1
w2
.
.
.
wn

The first line of the input contains the integer N (1 ≤ N ≤ 200) and the integer W (1 ≤ W ≤ 10,000), in that order, separated by a space. The integer N is the number of friends, and the integer W is the weight limit for carrying at once. If the total weight is greater than W, I cannot carry them.

The following N lines contain integers giving the weights of the friends. The integer wi (1 ≤ wi ≤ 10,000) is the weight of the i-th friend.

Output

Find how many combinations of friends can be in the backpack in the end. Print the total modulo 1,000,000,007. Note that 1,000,000,007 is prime.

Note that the case where nobody is in the backpack counts as one combination.

Examples3

Example 1
Input
```
4 8
1
2
7
9
```
Expected output
```
2
```
Example 2
Input
```
4 25
20
15
20
15
```
Expected output
```
4
```
Example 3
Input
```
6 37
5
9
13
18
26
33
```
Expected output
```
6
```