k-distribution

You are given N positive integers A1, A2, ... AN. Find the number of ways to distribute them in 2 groups in such a way that sum of numbers in each group is greater or equal K. The answer can be large so output it modulo 10^9 + 7.

Input
The first line contains two space-separated integers N and K.
The second line contains N space-separated integers: A1, A2, ... AN.

Output
Output one integer - answer for the question modulo 10^9 + 7.

Constraints
 0 < N  ≤ 100
 0 < Ai  ≤ 10^9
 0 < K  ≤ 10^5
 0 < N  ≤ 20 in 28 % of the test data.

SAMPLE INPUT
2 5
6 6


SAMPLE OUTPUT
2

Source: hackerearth | Difficulty: MEDIUM_HARD
Tags: Dynamic programming


Solutions:
MOD=1000000007
N,K=list(map(int,input().split()))
A=list(map(int,input().split()))
found=[0]*K
found[0]=1
Kplus=0
if sum(A)<2*K: 
	print(0)
	exit()
for a in A:
	Kplus=Kplus*2
	for j in range(max(0,K-a),K):
		Kplus+=found[j]
	Kplus%=MOD	
	for j in range(K-1,a-1,-1):
		found[j]=(found[j]+found[j-a])%MOD
print((MOD+Kplus-sum(found)%MOD)%MOD)