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;
    static int64_t pre[M][M][M];
    for(int n=0; n<=X; n++) for(int s=0; s<=X; s++) pre[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++){
        pre[i+1][n][s] = max(0, s-(L[i]-1)*n) * pre[i][n][s] % MOD;
    }

    static int64_t dp[2][M][M];
    dp[X%2][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; (x+1)*n<=X; n++) for(int s=0; s<=X; s++){
            int64_t bef = dp[x%2][n][s];
            if(bef == 0) continue;
            if(n == 0 && pt < N-1) continue;
            if(n > 0) mul(bef, inv_mod(pre[pt+1][n][s]));

            for(int k=0; s+x*k<=X; k++){
                int n2 = n+k, s2 = s+x*k;
                int64_t res = bef;
                if(n2 > 0) mul(res, pre[pt+1][n2][s2] * comb_mod(n2, k) % MOD);
                add(dp[(x-1)%2][n2][s2], res);
            }
        }
        for(int n=0; n<=X; n++) for(int s=0; s<=X; s++) dp[x%2][n][s] = 0;
    }

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