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 int MAXN = 505;
const int MOD = 1000000007;

int add(int x, int y) { return ((x += y) >= MOD) ? x - MOD : x; }
int sub(int x, int y) { return ((x -= y) < 0) ? x + MOD : x; }
int mul(int x, int y) { return (long long) x * y % MOD; }

int N, X;
int cnt[MAXN];
int C[MAXN][MAXN];
int pw[MAXN][MAXN];
int dp[MAXN][MAXN];
int ndp[MAXN][MAXN];

int main() {
   ios_base::sync_with_stdio(false);
   for (int i = 0; i < MAXN; ++i) {
      pw[i][0] = 1;
      for (int j = 1; j < MAXN; ++j) {
         pw[i][j] = mul(pw[i][j - 1], i);
      }
   }
   for (int i = 0; i < MAXN; ++i) {
      C[i][0] = 1;
      for (int j = 1; j <= i; ++j) {
         C[i][j] = add(C[i - 1][j], C[i - 1][j - 1]);
      }
   }
   cin >> N >> X;
   for (int i = 0; i < N; ++i) {
      int L;
      cin >> L;
      ++cnt[L];
   }
   dp[0][0] = 1;
   for (int len = X; len > 0; --len) {
      for (int numSeg = 0; numSeg <= X; ++numSeg) {
         for (int totLen = 0; totLen <= X; ++totLen) {
            if (dp[numSeg][totLen] == 0) continue;
            for (int addSeg = 0; totLen + addSeg * len <= X; ++addSeg) {
               int newSeg = numSeg + addSeg;
               int newLen = totLen + addSeg * len;
               ndp[newSeg][newLen] = add(ndp[newSeg][newLen], mul(dp[numSeg][totLen], C[newSeg][numSeg]));
            }
         }
      }
      for (int numSeg = 0; numSeg <= X; ++numSeg) {
         for (int totLen = 0; totLen <= X; ++totLen) {
            dp[numSeg][totLen] = ndp[numSeg][totLen];
            ndp[numSeg][totLen] = 0;
         }
      }
      for (int numSeg = 0; numSeg <= X; ++numSeg) {
         for (int totLen = 0; totLen <= X; ++totLen) {
            if (dp[numSeg][totLen]) {
               dp[numSeg][totLen] = mul(dp[numSeg][totLen], pw[totLen - numSeg * (len - 1)][cnt[len]]);
            }
         }
      }
   }
   int ans = 0;
   for (int numSeg = 0; numSeg <= X; ++numSeg) {
      for (int totLen = 0; totLen <= X; ++totLen) {
         if (dp[numSeg][totLen]) {
            int emptySpace = X - totLen;
            if (emptySpace < numSeg - 1) continue;
            int curValue = mul(dp[numSeg][totLen], C[emptySpace + 1][numSeg]);
            if (emptySpace & 1) {
               ans = sub(ans, curValue);
            } else {
               ans = add(ans, curValue);
            }
         }
      }
   }
   cout << ans << "\n";
   return 0;
}