Problem: Niwango bought a piece of land that can be represented as a half-open interval [0, X).

Niwango will lay out N vinyl sheets on this land. The sheets are numbered 1,2, \ldots, N, and they are distinguishable. For Sheet i, he can choose an integer j such that 0 \leq j \leq X - L_i and cover [j, j + L_i) with this sheet.

Find the number of ways to cover the land with the sheets such that no point in [0, X) remains uncovered, modulo (10^9+7). We consider two ways to cover the land different if and only if there is an integer i (1 \leq i \leq N) such that the region covered by Sheet i is different.

Constraints

* 1 \leq N \leq 100
* 1 \leq L_i \leq X \leq 500
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N X
L_1 L_2 \ldots L_N


Output

Print the answer.

Examples

Input

3 3
1 1 2


Output

10


Input

18 477
324 31 27 227 9 21 41 29 50 34 2 362 92 11 13 17 183 119


Output

134796357

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
typedef long long ll;
#define mod 1000000007
ll gi(){
	ll x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))f^=ch=='-',ch=getchar();
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	return f?x:-x;
}
std::mt19937 rnd(time(NULL));
#define rand rnd
#define pr std::pair<int,int>
#define fi first
#define se second
template<class T>void cxk(T&a,T b){a=a>b?a:b;}
template<class T>void cnk(T&a,T b){a=a<b?a:b;}
#ifdef mod
int pow(int x,int y){
	int ret=1;
	while(y){
		if(y&1)ret=1ll*ret*x%mod;
		x=1ll*x*x%mod;y>>=1;
	}
	return ret;
}
template<class Ta,class Tb>void inc(Ta&a,Tb b){a=a+b>=mod?a+b-mod:a+b;}
template<class Ta,class Tb>void dec(Ta&a,Tb b){a=a>=b?a-b:a+mod-b;}
#endif
int L[510],f[510][510][510];
int fact[510],ifact[510],pw[510][510];
int C(int n,int m){return 1ll*fact[n]*ifact[m]%mod*ifact[n-m]%mod;}
int Fill(int n,int m){if(m<0)return!n;if(!n||!m)return!n&&!m;if(n<m)return 0;return C(n-1,m-1);}
int main(){
#ifdef LOCAL
	freopen("in.in","r",stdin);
	//freopen("out.out","w",stdout);
#endif
	int n=gi(),X=gi();
	for(int i=1;i<=n;++i)++L[gi()];
	fact[0]=1;for(int i=1;i<=X;++i)fact[i]=1ll*fact[i-1]*i%mod;
	ifact[X]=pow(fact[X],mod-2);for(int i=X;i;--i)ifact[i-1]=1ll*ifact[i]*i%mod;
	f[X][0][0]=1;
	for(int i=0;i<=X;++i){
		pw[i][0]=1;
		for(int j=1;j<=n;++j)pw[i][j]=1ll*pw[i][j-1]*i%mod;
	}
	for(int i=X;i;--i)
		for(int j=0;j<=X;++j)
			for(int k=0;k<=X;++k)
				if(f[i][j][k])
					for(int c=0,nj=j,nk=k;nj<=X&&nk<=X;++c,nj+=i,nk++)
						inc(f[i-1][nj][nk],1ll*f[i][j][k]*ifact[c]%mod*pw[nj-nk*(i-1)][L[i]]%mod);
	int ans=0;
	for(int j=X,M=1;~j;--j,M=mod-M)
		for(int k=X;~k;--k)
			if(f[0][j][k])
				for(int o=0;o<=X-j;++o)
					inc(ans,1ll*f[0][j][k]*M%mod*Fill(o,k-1)%mod*(X-j-o+1)%mod*fact[k]%mod);
	printf("%d\n",ans);
	return 0;
}