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>
using namespace std;
#define ll long long
const int mod=1e9+7;

int add(int a, int b){ a+=b;return a>=mod?a-mod:a;}
void ckadd(int &a, int b){ a=add(a,b);}
int sub(int a, int b){ a-=b;return a<0?a+mod:a;}
void cksub(int &a, int b){ a=sub(a,b);}
int mul(int a, int b){ return (ll)a*b%mod;}
void ckmul(int &a, int b){ a=mul(a,b);}
int powmod(int x, int k){ int ans=1;for(;k;k>>=1,ckmul(x,x)) if(k&1) ckmul(ans,x);return ans;}
int inv(int x){ return powmod(x,mod-2);}

const int N=105;
const int X=505;
int dp[2][N][X],l[N],sum[X],sum_dp[X],sum_nunc[X];
int main()
{
	int n,x;
	scanf("%i %i",&n,&x);
	for(int i=1;i<=n;i++) scanf("%i",&l[i]);

	//srand(time(0));
	//n=100;
	//x=500;
	//for(int i=1;i<=n;i++) l[i]=rand()%x+1;

	sort(l+1,l+1+n);
	reverse(l+1,l+1+n);
	int now=1,las=0;
	dp[las][1][x-l[1]]=1;
	for(int i=2;i<=n;i++)
	{
		for(int groups=1;groups<=i;groups++)
		{
			sum[0]=0;
			for(int unc=1;unc<=x;unc++) sum[unc]=add(sum[unc-1],mul(dp[las][groups][unc],groups*2));

			sum_dp[0]=dp[las][groups+1][0];
			for(int unc=1;unc<=x;unc++) sum_dp[unc]=add(sum_dp[unc-1],dp[las][groups+1][unc]);

			sum_nunc[0]=0;
			for(int nunc=1;nunc<=x;nunc++) sum_nunc[nunc]=add(sum_nunc[nunc-1],mul(nunc,dp[las][groups+1][nunc]));

			for(int unc=0;unc<=x;unc++)
			{
				dp[now][groups][unc]=0;
				dp[now][groups][unc]=mul(dp[las][groups][unc],x-unc-(l[i]-1)*groups);
				//printf("(%i %i %i): %i\n",i,groups,unc,dp[now][groups][unc]);

				int tmp=0;
				ckadd(tmp,mul(l[i]-1+unc,sub(sum_dp[min(x,unc+l[i]-2)],unc==0?0:sum_dp[unc-1])));
				cksub(tmp,sub(sum_nunc[min(x,unc+l[i]-2)],unc==0?0:sum_nunc[unc-1]));
				ckadd(dp[now][groups][unc],mul(groups,tmp));
				//for(int gap=0;gap<=l[i]-2;gap++)
				//	if(unc+gap<=x) ckadd(dp[now][groups][unc],mul(dp[las][groups+1][unc+gap],mul(groups,l[i]-gap-1)));
				//printf("(%i %i %i): %i\n",i,groups,unc,dp[now][groups][unc]);
				if(unc+l[i]<=x) ckadd(dp[now][groups][unc],mul(dp[las][groups-1][unc+l[i]],groups));
				//printf("(%i %i %i): %i\n",i,groups,unc,dp[now][groups][unc]);

				ckadd(dp[now][groups][unc],sub(sum[min(x,unc+l[i]-1)],sum[unc]));
				//for(int gap=1;gap<=l[i]-1;gap++)
				//	if(unc+gap<=x) ckadd(dp[now][groups][unc],mul(dp[las][groups][unc+gap],2*groups));
				//printf("(%i %i %i): %i\n",i,groups,unc,dp[now][groups][unc]);
			}
		}
		swap(now,las);
	}
	int ans=0;
	for(int i=1;i<=n;i++) ckadd(ans,dp[las][i][0]);
	printf("%i\n",ans);
	return 0;
}