思路

dp。

先将所有磁铁按 $r_i$ 从小到大排序，然后令 $f_{i,j,k}$ 表示考虑了前 $i$ 个磁铁，分为 $j$ 组，占用的空位数为 $k$ 的方案数。

那么我们有三个转移：

• 第 $i$ 个磁铁单独成为了一个新组：$f_{i,j,k} \to f_{i-1,j-1,k-1}$。

• 第 $i$ 个磁铁接在前面 $j$ 个组的端点：$f_{i,j,k} \to f_{i,j,k} + f_{i-1,j,k-a_i} \times j \times 2$（$k \ge a_i$）

• 第 $i$ 个磁铁连接前面 $j+1$ 个组的两个：$f_{i,j,k} \to f_{i,j,k} + f_{i-1,j+1,k-2 \times a_i+1} \times j \times (j+1)$（$k \ge 2 \times a_i - 1$）。

最后我们得到了所有磁铁分为 $1$ 组长度为 $i$ 的方案数，那么它对答案的贡献为 $f_{n,1,i} \times \binom{l-i+n}{n}$（根据插板法易得）。

那么这题就做完了，时间复杂度 $O(n^2 \times l)$。

/*

p_b_p_b txdy
AThousandMoon txdy
AThousandSuns txdy
hxy txdy

*/

#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define scd second

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;

const int maxn = 55;
const int maxm = 10200;
const ll mod = 1000000007;

ll n, m, a[maxn], fac[maxm], inv[maxm], f[maxn][maxn][maxm];

void prepare() {
	fac[0] = 1;
	for (int i = 1; i <= 10100; ++i) {
		fac[i] = fac[i - 1] * i % mod;
	}
	inv[1] = 1;
	for (int i = 2; i <= 10100; ++i) {
		inv[i] = (mod - mod / i) * inv[mod % i] % mod;
	}
	inv[0] = 1;
	for (int i = 1; i <= 10100; ++i) {
		inv[i] = inv[i - 1] * inv[i] % mod;
	}
}

ll C(ll n, ll m) {
	if (n < m) {
		return 0;
	} else {
		return fac[n] * inv[m] % mod * inv[n - m] % mod;
	}
}

void solve() {
	scanf("%lld%lld", &n, &m);
	for (int i = 1; i <= n; ++i) {
		scanf("%lld", &a[i]);
	}
	sort(a + 1, a + n + 1);
	f[0][0][0] = 1;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= i; ++j) {
			for (int k = 1; k <= m; ++k) {
				f[i][j][k] = f[i - 1][j - 1][k - 1];
				if (k >= a[i]) {
					f[i][j][k] = (f[i][j][k] + f[i - 1][j][k - a[i]] * j * 2) % mod;
				}
				if (k >= 2 * a[i] - 1) {
					f[i][j][k] = (f[i][j][k] + f[i - 1][j + 1][k - a[i] * 2 + 1] * j % mod * (j + 1)) % mod;
				}
			}
		}
	}
	ll ans = 0;
	for (int i = 1; i <= m; ++i) {
		ans = (ans + f[n][1][i] * C(m - i + n, n)) % mod;
	}
	printf("%lld", ans);
}

int main() {
	prepare();
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}