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:
// ※※※ 解答不能 ※※※
// semiexp氏.
// https://atcoder.jp/contests/dwacon6th-prelims/submissions/9424749
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repx(i, a, b) for(int i = a; i < b; i++)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
const LL MOD = 1e9 + 7;
#define ADD(X, Y) ((X) = ((X) + (Y) % MOD) % MOD)

int N, X, L[110];
LL dp[2][550][550]; // *, num segments, total length
int cnt[550];

LL invs[101010];
LL fact[101010], facti[101010], sums[101010];
LL C[1010][1010];

LL modpow(LL x, int p = MOD - 2){
    if(p == 0) return 1;
    LL tmp = modpow(x, p / 2);
    tmp = tmp * tmp % MOD;
    if(p % 2 == 1) tmp = tmp * x % MOD;
    return tmp;
}

LL comb(int x, int y){
    if(0 <= y && y <= x) return C[x][y];
    return 0;
}

LL waf(int x, int y){
    // x holes, y items
    return comb(x + y - 1, y);
}

int main(){
    scanf("%d %d", &N, &X);
    rep(i, N) scanf("%d", L + i);
    rep(i, N) ++cnt[L[i]];
    C[0][0] = 1;
    repx(i, 1, 1001){
        C[i][0] = 1;
        repx(j, 1, 1001) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
    }
    
    repx(i, 1, 1001) invs[i] = modpow(i);
    fact[0] = facti[0] = 1;
    repx(i, 1, 1001){
        fact[i] = fact[i - 1] * i % MOD;
        facti[i] = facti[i - 1] * invs[i] % MOD;
    }
    int t = 0;
    rep(j, X + 1) rep(k, X + 1) dp[t][j][k] = 0;
    dp[t][0][0] = 1;
    repr(i, X, 1){
        rep(j, X + 1) rep(k, X + 1) dp[1 - t][j][k] = 0;
        rep(j, X + 1){
            rep(k, X + 1){
                if(dp[t][j][k] == 0) continue;
                int s = k;
                for(int l = 0; s <= X; ++l, s += i) {
                    ADD(dp[1 - t][j + l][s], dp[t][j][k] * facti[l] % MOD);
                }
            }
        }
        rep(r, cnt[i]){
            rep(j, X + 1){
                rep(k, X + 1){
                    if(dp[1 - t][j][k]) dp[1 - t][j][k] = dp[1 - t][j][k] * max(0, k - j * (i - 1)) % MOD;
                }
            }
        }
        t = 1 - t;
    }
    LL ret = 0;
    repx(i, 1, X + 1){
        rep(j, X + 1){
            LL bas = dp[t][i][j];
            int n_range = i;
            int n_blank = X - j;
            LL tmp = bas * fact[i] % MOD * waf(n_range + 1, n_blank - n_range + 1) % MOD;
            if(n_blank % 2 == 1) tmp = MOD - tmp;
            ADD(ret, tmp);
        }
    }
    printf("%lld\n", ret);
    return 0;
}