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 <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define MOD 1000000007
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

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

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

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

i64 comb(int x, int y)
{
	if (0 <= y && y <= x) return C[x][y];
	return 0;
}
i64 waf(int x, int y)
{
	// x holes, y items
	return comb(x + y - 1, y);
}

int main()
{
	scanf("%d%d", &N, &X);
	for (int i = 0; i < N; ++i) scanf("%d", L + i);
	for (int i = 0; i < N; ++i) ++cnt[L[i]];
	C[0][0] = 1;
	for (int i = 1; i <= 1000; ++i) {
		C[i][0] = 1;
		for (int j = 1; j <= 1000; ++j) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
	}

	for (int i = 1; i <= 1000; ++i) invs[i] = modpow(i);
	fact[0] = facti[0] = 1;
	for (int i = 1; i <= 1000; ++i) {
		fact[i] = fact[i - 1] * i % MOD;
		facti[i] = facti[i - 1] * invs[i] % MOD;
	}

	int t = 0;
	for (int j = 0; j <= X; ++j) {
		for (int k = 0; k <= X; ++k) {
			dp[t][j][k] = 0;
		}
	}
	dp[t][0][0] = 1;
	for (int i = X; i >= 1; --i) {
		for (int j = 0; j <= X; ++j) {
			for (int k = 0; k <= X; ++k) {
				dp[1 - t][j][k] = 0;
			}
		}
		for (int j = 0; j <= X; ++j) {
			for (int k = 0; k <= X; ++k) {
				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);
				}
			}
		}
		for (int r = 0; r < cnt[i]; ++r) {
			for (int j = 0; j <= X; ++j) {
				for (int k = 0; k <= X; ++k) {
					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;
	}
	i64 ret = 0;
	for (int i = 1; i <= X; ++i) {
		for (int j = 0; j <= X; ++j) {
			i64 bas = dp[t][i][j];
			int n_range = i;
			int n_blank = X - j;
			i64 tmp = bas * fact[i] % MOD * waf(n_range + 1, n_blank - n_range + 1) % MOD;
			//printf("%d %d: %lld %lld\n", i, j, bas, tmp);
			if (n_blank % 2 == 1) tmp = MOD - tmp;
			ADD(ret, tmp);
		}
	}
	printf("%lld\n", ret);
	return 0;
}