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 fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ar array

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 105, mod = 1e9 + 7;

int f[maxn][maxn][505], a[maxn];
int N, X, l[maxn];

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL
  cin >> N >> X;
  for(int i = 1; i <= N; ++i)
    cin >> l[i];
  sort(l + 1, l + 1 + N, greater<int>());
  function<void(int &, int)>add = [&](int & x, int y)
  {
    x += y;
    if(x >= mod) x -= mod;
    if(x < 0) x += mod;
  };
  f[1][1][l[1]] = 1;
  for(int i = 2; i <= N; ++i){
    for(int j = 1; j <= i; ++j){
      for(int k = j * l[i - 1]; k <= X; ++k){
        int v = f[i - 1][j][k];
        add(f[i][j + 1][k + l[i]], 1ll * (j + 1) * v % mod);
        add(f[i][j][k], 1ll * (k - j * (l[i] - 1)) * v % mod);
        for(int t = 1; t < l[i]; ++t)
          add(f[i][j][k + l[i] - t], 2ll * j * v % mod);
        if(j > 1){
          for(int t = 2; t <= l[i]; ++t)
            add(f[i][j - 1][k + l[i] - t], 1ll * (j - 1) * (t - 1) % mod * v % mod);
        }
      }
    }
  }
  int res = 0;
  for(int i = 1; i <= N; ++i)
    add(res, f[N][i][X]);
  cout << res;
}