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;

const int64_t MOD = 1e9+7;
void add(int64_t& a, int64_t b){
    a = (a+b) % MOD;
}
void mul(int64_t& a, int64_t b){
    a = a*b % MOD;
}

vector<int64_t> fact, seq_inv, fact_inv;

void create_fact_mod(int num){
    fact[0] = fact[1] = 1;
    for(int i=2; i<=num; i++) fact[i] = fact[i-1] * i % MOD;
}

void create_seq_inv_mod(int num){
    seq_inv[0] = seq_inv[1] = 1;
    for(int i=2; i<=num; i++) seq_inv[i] = (MOD - MOD/i) * seq_inv[MOD%i] % MOD;
}

void create_fact_inv_mod(int num){
    fact_inv[0] = fact_inv[1] = 1;
    for(int i=2; i<=num; i++) fact_inv[i] = fact_inv[i-1] * seq_inv[i] % MOD;
}

void create_mod_tables(int num){
    fact.resize(num+1);
    seq_inv.resize(num+1);
    fact_inv.resize(num+1);
    create_fact_mod(num);
    create_seq_inv_mod(num);
    create_fact_inv_mod(num);
}

int64_t comb_mod(int n, int k){
    return fact[n] * fact_inv[n-k] % MOD * fact_inv[k] % MOD;
}

int64_t perm_mod(int n, int k){
    return fact[n] * fact_inv[n-k] % MOD;
}

int64_t power_mod(int64_t num, int64_t power){
    int64_t prod = 1;
    num %= MOD;
    while(power > 0){
        if(power&1) prod = prod * num % MOD;
        num = num * num % MOD;
        power >>= 1;
    }
    return prod;
}

int64_t extgcd(int64_t a, int64_t b, int64_t& x, int64_t& y){
    int64_t d = a;
    if(b != 0){
        d = extgcd(b, a%b, y, x);
        y -= (a/b) * x;
    }else{
        x = 1; y = 0;
    }
    return d;
}

int64_t inv_mod(int64_t a){
    int64_t x, y;
    extgcd(a, MOD, x, y);
    return (MOD + x%MOD) % MOD;
}

int main(){
    int N, X;
    cin >> N >> X;
    vector<int> L(N);
    for(int i=0; i<N; i++) cin >> L[i];
    sort(L.begin(), L.end());
    create_mod_tables(2*X);

    const int M = 510;

    int64_t small_invs[M];
    for(int i=1; i<=X; i++) small_invs[i] = inv_mod(i);

    static int64_t pre[M][M][M], pre_inv[M][M][M];
    for(int n=0; n<=X; n++) for(int s=0; s<=X; s++) pre[0][n][s] = pre_inv[0][n][s] = 1;
    for(int i=0; i<N; i++) for(int n=0; n<=X; n++) for(int s=0; s<=X; s++){
        int v = max(1, s-(L[i]-1)*n);
        pre[i+1][n][s] = v * pre[i][n][s] % MOD;
        pre_inv[i+1][n][s] = small_invs[v] * pre_inv[i][n][s] % MOD;
    }

    static int64_t dp[2][M][M][2];
    dp[X%2][0][0][0] = 1;
    int pt = N-1;
    for(int x=X; x>0; x--){
        while(pt >= 0 && L[pt] > x) pt--;
        for(int n=0; n<=X; n++) for(int s=0; s<=X; s++) for(int f=0; f<2; f++){
            if(f == 0 && pt < N-1) continue;
            int64_t bef = dp[x%2][n][s][f] * pre_inv[pt+1][n][s] % MOD;
            if(bef == 0) continue;
            
            for(int k=0; s+x*k+n+k-1<=X; k++){
                int n2 = n+k, s2 = s+x*k, f2 = f|(k>0);
                int64_t res = bef * pre[pt+1][n2][s2] % MOD * comb_mod(n2, k) % MOD;
                add(dp[(x-1)%2][n2][s2][f2], res);
            }
        }
        for(int n=0; n<=X; n++) for(int s=0; s<=X; s++) for(int f=0; f<2; f++) dp[x%2][n][s][f] = 0;
    }

    int64_t ans = 0;
    for(int n=1; n<=X; n++) for(int s=0; s+n-1<=X; s++){
        int rest = X - (s+n-1);
        int64_t res = comb_mod(rest+n, n) * dp[0][n][s][1] % MOD;
        int blank = X-s;
        if(blank%2) res = MOD-res;
        add(ans, res);
    }
    cout << ans << endl;
    return 0;
}