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 XX first
#define YY second
#define pb emplace_back
#define FOR(i,a,b) for(int (i)=(a);i<(b);++(i))
#define EFOR(i,a,b) for(int (i)=(a);i<=(b);++(i))
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define REP rep
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define all(X) (X).begin(),(X).end()
#define eb emplace_back

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef ll LL;
typedef pii PII;
typedef pll PLL;
const ll MOD=1e9+7;

#define rall(X) (X).rbegin(),(X).rend()
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rreps(X,S,Y) for (int (X) = (Y)-1;(X) >= (S);--(X))
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}

template<ll mod>
struct ModInt{
  using M=ModInt;
  ll a;
  M& put(ll v){
    a=(v<mod)?v:v-mod;
    return *this;
  }
  ModInt(ll v=0){put(v%mod+mod);}
  M operator+(M x){return M().put(a+x.a);}
  M operator-(M x){return M().put(a+mod-x.a);}
  M operator*(M x){return M().put(a*x.a%mod);}
  M operator/(M x){return x.inv()*a;}
  M& operator+=(M x){return *this=*this+x;};
  M& operator-=(M x){return *this=*this-x;};
  M& operator*=(M x){return *this=*this*x;};
  M& operator/=(M x){return *this=*this/x;};
  bool operator==(M x){return a==x.a;}
  M pow(ll m) {
    M x=*this,res=1;
    while(m){
      if(m&1)res*=x;
      x*=x;
      m>>=1;
    }
    return res;
  }
  M inv(){return pow(mod-2);}
};
using mint = ModInt<MOD>;

int N;
int X;
vector<int> L;
mint dp[114][114][1014];
mint imos[114][114][1014];
mint dimos[114][114][1014];
mint fact[514];

signed main(){
  ios_base::sync_with_stdio(false);
  cout<<fixed<<setprecision(0);
  cin >> N >> X;
  rep(i, N) {
    int l;
    cin >> l;
    L.eb(l);
  }
  fact[0] = 1;
  reps(i, 1, X+10) fact[i] = fact[i-1]*i;
  sort(all(L));
  reverse(all(L));
  dp[0][1][L[0]] = 1;
  reps(i, 1, N) {
    reps(cnt, 1, N+1) {
      reps(l, 1, X+1) {
        auto &v = dp[i-1][cnt][l];
        // append  
        dp[i][cnt+1][l+L[i]] += v;
        // include
        if (l-cnt*(L[i]-1) > 0) {
          dp[i][cnt][l] += v * (l-cnt*(L[i]-1));
        } 
        imos[i][cnt][l+1] += v * 2 * cnt;
        imos[i][cnt][l+L[i]] -= v * 2 * cnt;
        // merge
        if (cnt >= 2 && L[i] >= 2) {
          mint val = v*cnt*(cnt-1);
          dimos[i][cnt-1][l+L[i]-2] += val;
          if (l > 0) {
            dimos[i][cnt-1][l-1] -= val;
            imos[i][cnt-1][1] -= val*(L[i]-1);
            imos[i][cnt-1][l] += val*(L[i]-1);
          }
        }
      }
    }
    rep(cnt, N+1) {
      rreps(l, 1, X+X+1) {
        dimos[i][cnt][l] += dimos[i][cnt][l+1];
      }
      rreps(l, 1, X+X+1) {
        dimos[i][cnt][l] += dimos[i][cnt][l+1];
      }
      reps(l, 1, X+1) {
        imos[i][cnt][l] += imos[i][cnt][l-1];
        dp[i][cnt][l] += imos[i][cnt][l];
        dp[i][cnt][l] += dimos[i][cnt][l];
      }
    }
  }

  mint ans = 0;
  rreps(cnt, 1, N+1) {
    dp[N-1][cnt][X] *= fact[cnt];
    //cout << cnt << ": " << dp[N-1][cnt][X].a << endl;
  }
  rreps(cnt, 1, N+1) {
    auto val = dp[N-1][cnt][X];
    //if (cnt%2) ans += val;
    //else ans -= val;
    ans += val;
  }
  cout << ans.a << endl;
}