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 pb push_back
#define mp make_pair
#define taskname "A"
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
const int maxn = 2e5 + 5;
const int mod = 1e9 + 7;
 
int dp[2][101][501];
int n ,  x;
vector<int> val;
void add(int & x , ll y){
    x += y % mod;
    if(x >= mod)x -= mod;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    cin >> n >> x;
    val.resize(n);
    for(auto & c : val)cin >> c;
    sort(val.begin(),val.end(),greater<int>());
    bool bit = 0;dp[0][0][0] = 1;
    for(auto & l : val){
        for(int i = 0 ; i <= n ; ++i){
            for(int j = 0 ; j <= x ; ++j){
                if(dp[bit][i][j] > 0){
                    if(j + l <= x)add(dp[!bit][i + 1][j + l],(ll)dp[bit][i][j] * (i + 1));
                    if(i >= 1){
                        add(dp[!bit][i][j] , (ll)dp[bit][i][j] * (j - i * (l - 1)));
                        for(int k = 1 ; k <= l && k + j <= x ; ++k){
                            add(dp[!bit][i][j+k],(ll)dp[bit][i][j]*i*2);
                            if(i >= 2){
                                add(dp[!bit][i-1][j+k],(ll)dp[bit][i][j]*(l-k+1)*(i-1));
                            }
                        }
                    }
                    dp[bit][i][j] = 0;
                }
            }
        }
        bit ^= 1;
    }
    cout << dp[bit][1][x];
}