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:
//Zory-2020
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
// typedef __int128 ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define FR first
#define SE second
#define MP make_pair
#define PB push_back
#define vc vector
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define bin(x) (1ll<<(x))
#define fo(i,l,r) for(int i=(l),I=(r);i<=I;i++)
#define fd(i,r,l) for(int i=(r),I=(l);i>=I;i--)
#define Debug printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define debug(x) cerr<<#x<<'='<<x<<endl
#define mem(x,val) memset(x,val,sizeof x)
namespace mine
{
    ll qread()
    {
        ll ans=0,f=1;char c=getchar();
        while(c<'0' or c>'9') {if(c=='-')f=-1;c=getchar();}
        while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
        return ans*f;
    }
    void write(ll num){if(num<0) putchar('-'),num=-num;if(num>=10) write(num/10);putchar('0'+num%10);}
    void write1(ll num){write(num);putchar(' ');}
    void write2(ll num){write(num);putchar('\n');}
    template<typename T>inline bool chmax(T&a,const T&b){return a<b?a=b,1:0;}
    template<typename T>inline bool chmin(T&a,const T&b){return a>b?a=b,1:0;}
    ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
    bool IN(ll x,ll l,ll r){return l<=x and x<=r;}

    const int INF=0x3f3f3f3f;
    const int MOD=1e9+7;
    int mm(const int x){return x>=MOD?x-MOD:x;}
    template<typename T> void add(T &x,const int &y){x=(x+y>=MOD?x+y-MOD:x+y);}
    ll qpower(ll x,ll e,int mod=MOD){ll ans=1;while(e){if(e&1)ans=ans*x%mod;x=x*x%mod;e>>=1;}return ans;}
    ll invm(ll x){return qpower(x,MOD-2);}
    const int N=1e3+10;

    ll fac[N],facinv[N];ll C(int n,int m){return (n<0 or n<m)?0:fac[n]*facinv[m]%MOD*facinv[n-m]%MOD;}
    int ct[N],pw[N][N];
    int f[N][N],g[N][N];
    void main()
	{
        fac[0]=1;fo(i,1,N-1) fac[i]=fac[i-1]*i%MOD;
        facinv[N-1]=invm(fac[N-1]);fd(i,N-1,1) facinv[i-1]=facinv[i]*i%MOD;
        int n=qread(),X=qread();fo(i,1,n) ct[qread()]++;g[0][0]=1;
        fo(i,0,X) fo(j,0,n) pw[i][j]=qpower(i,j);
        fd(now,X,1)
        {
            fo(cnt,0,(X+1)/2) fo(len,cnt*(now+1),X-(cnt-1)) if(g[cnt][len])
                fo(i,0,min((X-cnt+1-len)/now,(X+1)/2-cnt))
                // for(int i=0;cnt+i<=(X+1)/2 and len+i*now<=X-cnt+1;i++) 
                    add(f[cnt+i][len+i*now],1ll*g[cnt][len]*facinv[i]%MOD );  
            fo(cnt,0,(X+1)/2) fo(len,cnt*now,X-(cnt-1))
            {
                g[cnt][len]=1ll*f[cnt][len]*pw[len+cnt*(-now+1)][ct[now]]%MOD;
                f[cnt][len]=0;
            }
        }
        ll ans=0;fo(cnt,0,X) fo(len,0,X)
            add(ans, fac[cnt]*g[cnt][len]%MOD*C(X-len+2-1,cnt)%MOD*((X-len)&1?MOD-1:1)%MOD );write(ans);
	}
};//(ans+MOD)%MOD
signed main()
{
    srand(time(0));
    mine::main();
}