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>
#define ll long long
#define ull unsigned ll
#define uint unsigned
#define pii pair<int,int>
#define pll pair<ll,ll>
#define IT iterator
#define PB push_back
#define fi first
#define se second
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define CLR(a,v) memset(a,v,sizeof(a));
#define CPY(a,b) memcpy(a,b,sizeof(a));
#define debug puts("wzpakking")
#define y1 ysghysgsygsh
using namespace std;
const int mo=1000000007;
const int N=1005;
int n,X,x,ans;
int cnt[N],a[N];
int C[N][N],f[N][N];
int inv[N];
void init(){
	inv[0]=inv[1]=1;
	For(i,2,N-1) inv[i]=1ll*inv[mo%i]*(mo-mo/i)%mo;
	For(i,1,N-1) inv[i]=1ll*inv[i-1]*inv[i]%mo;
	For(i,0,N-1) C[i][0]=1;
	For(i,1,N-1) For(j,1,i)
		C[i][j]=(C[i-1][j]+C[i-1][j-1])%mo;
}
int power(int x,int y){
	int s=1;
	for (;y;y/=2,x=1ll*x*x%mo)
		if (y&1) s=1ll*s*x%mo;
	return s;
}
int main(){
	init();
	scanf("%d%d",&n,&X);
	For(i,1,n) scanf("%d",&x),++cnt[x]; 
	f[0][0]=1;
	Rep(i,X,1){
		Rep(j,X/i,0) For(k,1,X/i-j) For(L,0,X-k*i)
			f[j+k][L+k*i]=(f[j+k][L+k*i]+1ll*f[j][L]*C[j+k][k])%mo;
		For(j,0,X/i) For(k,j*i,X){
			int v=k-j*(i-1);
			f[j][k]=1ll*f[j][k]*power(v,cnt[i])%mo;
		}
	}
	For(i,1,X) For(j,0,X){
		int tr=C[X-j+1][i];
		//if (tr) printf("%d %d %d\n",i,j,f[i][j]);
		if ((X-j)&1) tr=(mo-tr);
		ans=(ans+1ll*tr*f[i][j])%mo;	
	}
	printf("%d\n",ans);
}
/*
18 500
324 31 27 227 9 21 41 29 50 34 2 362 92 11 13 17 183 119
*/