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 rep(i, N) for (int i = 0; i < (N); i++)
#define all(a) (a).begin(), (a).end()
#define pb push_back

using ll = long long;
using i_i = tuple<int, int>;

const int MOD = 1e9 + 7;

ll C[1010][1010];

int main() {
    for (int x = 0; x < 1010; x++) {
        C[x][0] = 1;
        for (int y = 1; y <= x; y++)
            C[x][y] = (C[x - 1][y - 1] + C[x - 1][y]) % MOD;
    }
    
    int N, X;
    cin >> N >> X;
    vector<int> a(X + 1);
    while (N--) {
        int l; cin >> l;
        a[l]++;
    }
    vector<vector<ll>> dp(X + 2, vector<ll>(X + 1));
    dp[0][0] = 1;
    for (int l = X; l >= 0; l--) {
        vector<vector<ll>> _dp(X + 2, vector<ll>(X + 1));
        for (int k = X + 1; k >= 0; k--) rep(x, X + 1) rep(dk, X + 1) {
            int _k = k + dk, _x = x + dk * l;
            if (_k + _x - 1 > X) break;
            ll z = dp[k][x] * C[_k][dk] % MOD;
            _dp[_k][_x] = (_dp[_k][_x] + z) % MOD;
        }
        dp = _dp;
        rep(k, X + 2) rep(x, X + 1) {
            if (k + x - 1 > X) break;
            ll y = x - k * (l - 1);
            rep(t, a[l]) dp[k][x] = dp[k][x] * y % MOD;
        }
    }
    ll ans = 0;
    rep(k, X + 2) rep(x, X + 1) if (k + x - 1 == X) {
        // cout << k << ' ' << x << ' ' << dp[k][x] << endl;
        ll z = dp[k][x];
        if (k % 2 == 0) z *= -1; 
        ans = (ans + z) % MOD;
    }
    cout << (ans + MOD) % MOD << endl;
}