I have a lot of friends. Every friend is very small.
I often go out with my friends. Put some friends in your backpack and go out together.
Every morning I decide which friends to go out with that day. Put friends one by one in an empty backpack.
I'm not very strong. Therefore, there is a limit to the weight of friends that can be carried at the same time.
I keep friends so that I don't exceed the weight limit. The order in which you put them in depends on your mood.
I won't stop as long as I still have friends to put in. I will never stop.


…… By the way, how many patterns are there in total for the combination of friends in the backpack?



Input

N W
w1
w2
..
..
..
wn


On the first line of input, the integer N (1 ≤ N ≤ 200) and the integer W (1 ≤ W ≤ 10,000) are written in this order, separated by blanks. The integer N represents the number of friends, and the integer W represents the limit of the weight that can be carried at the same time. It cannot be carried if the total weight is greater than W.

The next N lines contain an integer that represents the weight of the friend. The integer wi (1 ≤ wi ≤ 10,000) represents the weight of the i-th friend.

Output

How many possible combinations of friends are finally in the backpack? Divide the total number by 1,000,000,007 and output the remainder. Note that 1,000,000,007 are prime numbers.

Note that "no one is in the backpack" is counted as one.

Examples

Input

4 8
1
2
7
9


Output

2


Input

4 25
20
15
20
15


Output

4


Input

6 37
5
9
13
18
26
33


Output

6

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 13
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def main():
	rr = []

	def f(n, w):
		a = sorted([I() for _ in range(n)], reverse=True)
		dp = [0] * (w + 1)
		dp[0] = 1
		sm = sum(a)
		if sm <= w:
			return 1
		r = 0
		for c in a:
			sm -= c
			if w >= sm:
				r += sum(dp[max(0, w - sm - c + 1):w - sm + 1])
				r %= mod
			for j in range(w - c, -1, -1):
				dp[j + c] += dp[j]
				dp[j + c] %= mod
		return r % mod
	while 1:
		(n, m) = LI()
		if n == 0:
			break
		rr.append(f(n, m))
		break
	return '\n'.join(map(str, rr))
print(main())


(N, W) = map(int, input().split())
w = []
for i in range(N):
	w.append(int(input()))
w.sort()
summ = 0
ans = 0
for (num, wi) in enumerate(w):
	if num == N - 1:
		if sum(w) - w[-1] <= W and W - sum(w) - w[-1] < w[-1]:
			ans += 1
		break
	dp = [[0] * (W + 1) for i in range(N - num)]
	dp[0][0] = 1
	for n in range(N - num - 1):
		dpn1 = dp[n + 1]
		dpn = dp[n]
		for k in range(W + 1):
			if k - w[num + n + 1] >= 0:
				dpn1[k] = dpn[k] + dpn[k - w[num + n + 1]]
			else:
				dpn1[k] = dpn[k]
	for i in range(max(W - summ - wi + 1, 0), W - summ + 1):
		ans += dp[-1][i]
		ans %= 10 ** 9 + 7
	summ += wi
	if W < summ:
		break
print(ans % (10 ** 9 + 7))


(N, W) = map(int, input().split())
MOD = 10 ** 9 + 7
ws = [int(input()) for i in range(N)]
ws.sort(reverse=1)
su = sum(ws)
dp = [0] * (W + 1)
dp[0] = 1
ans = 0
if su <= W:
	ans += 1
for i in range(N):
	w = ws[i]
	su -= w
	ans += sum(dp[max(W + 1 - w - su, 0):max(W + 1 - su, 0)]) % MOD
	for j in range(W, w - 1, -1):
		dp[j] += dp[j - w]
		dp[j] %= MOD
print(ans % MOD)