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;

typedef long long lint;
typedef long double louble;

template<typename T1,typename T2> inline T1 max(T1 a,T2 b){return a<b?b:a;}
template<typename T1,typename T2> inline T1 min(T1 a,T2 b){return a<b?a:b;}

const char lf = '\n';

namespace ae86
{
	const int bufl = 1<<15;

	char buf[bufl],*s=buf,*t=buf;

	inline int fetch()
	{
		if(s==t){t=(s=buf)+fread(buf,1,bufl,stdin);if(s==t)return EOF;}
		return *s++;
	}

	inline int ty()
	{
		int a=0,b=1,c=fetch();
		while(!isdigit(c))b^=c=='-',c=fetch();
		while(isdigit(c))a=a*10+c-48,c=fetch();
		return b?a:-a;
	}
}
using ae86::ty;

const int _ = 1007 , mo = 1000000007;

inline lint powa(lint a,lint t)
{
	lint b=1;
	while(t){if(t&1)b=b*a%mo;a=a*a%mo,t>>=1;}
	return b;
}

inline lint inva(lint a)
{
	return powa(a,mo-2);
}

lint jc[_],rjc[_];

inline void fuck(int n=_-1)
{
	jc[0]=jc[1]=rjc[0]=1;
	for(int i=2;i<=n;i++)jc[i]=jc[i-1]*i%mo;
	rjc[n]=inva(jc[n]);
	for(int i=n-1;i>=1;i--)rjc[i]=rjc[i+1]*(1ll+i)%mo;
}

inline lint C(int n,int m)
{
	if(n<m || n<0 || m<0)return 0;
	return jc[n]*rjc[m]%mo*rjc[n-m]%mo;
}

int n,m,len[_],got[_]={0};
lint f[_][_]={0};

int main()
{
	ios::sync_with_stdio(0),cout.tie(nullptr);

	fuck();

	n=ty(),m=ty();
	for(int i=1;i<=n;i++)len[i]=ty(),got[len[i]]++;

	f[0][0]=1;
	for(int i=m;i>=1;i--)
	{
		for(int j=m;j>=1;j--)
			for(int k=i;k<=m;k++)
				for(int a=1;a<=j && a*i<=k;a++)
					f[j][k]=(f[j][k]+f[j-a][k-a*i]*rjc[a]%mo)%mo;
		if(got[i])
			for(int j=0;j<=m;j++)
				for(int k=0;k<=m;k++)
					f[j][k]=f[j][k]*powa(k-j*(i-1),got[i])%mo;
	}

	lint ans=0;
	for(int j=1;j<=m;j++)
	{
		for(int k=1;k<=m;k++)
		{
			if(!f[j][k])continue;
			lint sum=0;
			for(int a=0;a<j;a++)
				sum=(sum+((a&1)?mo-1ll:1ll)*C(j-1,a)%mo*C(m-k+j-a,m-k)%mo)%mo;
			sum=sum*f[j][k]%mo*jc[j]%mo;
			ans=(ans+(((m-k)&1)?mo-1ll:1ll)*sum%mo)%mo;
		}
	}

	cout<<ans<<lf;
	
	return 0;
}