#include <bits/stdc++.h>
#define se second
#define fs first
#define pb push_back
#define ll long long
#define ii pair<ll,ll>
#define ld long double
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
using namespace std;
mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }
const int N = 100 + 7;
const ll Mod = 1e9 + 7;
const int szBL = 916;
const ll INF = 1e9;
const int BASE = 137;
int n, L;
int a[N];
int dp[N][N * 10][N][3];
inline void add (int &a, int b) { a += b; if (a >= Mod) a -= Mod; }
void solution () {
cin >> n >> L;
rep (i, 1, n) cin >> a[i];
sort (a + 1, a + 1 + n);
dp[1][0][2][0] = 1;
dp[1][0][1][1] = 2;
rep (i, 1, n - 1) {
int D = a[i + 1] - a[i];
rep (j, 0, L)
rep (k, 0, n) {
int newcost = j + 2 * D * (k - 1);
if (newcost <= L && k >= 3) {
add (dp[i + 1][newcost][k][0], 1LL * dp[i][j][k][0] * 2 % Mod * (k - 2) % Mod);
add (dp[i + 1][newcost][k + 1][0], 1LL * dp[i][j][k][0] * (k - 2) % Mod);
add (dp[i + 1][newcost][k - 1][0], 1LL * dp[i][j][k][0] * (k - 2) % Mod);
// if (i + 1 == 3 && newcost == 4) {
// cout << i<<","<<j<<","<<k<<","<<0<<": "<<dp[i][j][k][0] <<"\n";
// }
}
if (newcost <= L && k >= 2) {
add (dp[i + 1][newcost][k - 1][1], 1LL * dp[i][j][k][0] * 2 % Mod);
add (dp[i + 1][newcost][k][1], 1LL * dp[i][j][k][0] * 2 % Mod);
add (dp[i + 1][newcost][k][0], 1LL * dp[i][j][k][0] * 2 % Mod);
add (dp[i + 1][newcost][k + 1][0], 1LL * dp[i][j][k][0] * 2 % Mod);
// if (i + 1 == 3 && newcost == 4) {
// cout << i<<","<<j<<","<<k<<","<<0<<": "<<dp[i][j][k][0] <<" ji\n";
// }
}
newcost = j + 2 * D * (k - 1) + D;
if (newcost <= L && k >= 2) {
add (dp[i + 1][newcost][k][1], 1LL * dp[i][j][k][1] * 2 % Mod * (k - 1) % Mod);
add (dp[i + 1][newcost][k + 1][1], 1LL * dp[i][j][k][1] * (k - 1) % Mod);
add (dp[i + 1][newcost][k - 1][1], 1LL * dp[i][j][k][1] * (k - 1) % Mod);
}
if (newcost <= L && k >= 1) {
add (dp[i + 1][newcost][k][2], dp[i][j][k][1]);
add (dp[i + 1][newcost][k - 1][2], dp[i][j][k][1]);
add (dp[i + 1][newcost][k][1], dp[i][j][k][1]);
add (dp[i + 1][newcost][k + 1][1], dp[i][j][k][1]);
}
newcost = j + 2 * D * k;
if (newcost <= L && k >= 1) {
add (dp[i + 1][newcost][k][2], 1LL * dp[i][j][k][2] * 2 % Mod * k % Mod);
add (dp[i + 1][newcost][k + 1][2], 1LL * dp[i][j][k][2] * k % Mod);
add (dp[i + 1][newcost][k - 1][2], 1LL * dp[i][j][k][2] * k % Mod);
// if (i + 1 == 3 && newcost == 3) {
// cout << i<<","<<j<<","<<k<<","<<2<<": "<<dp[i][j][k][2] <<" ji\n";
// }
}
}
}
ll res = 0;
rep (i, 0, L) {
(res += dp[n][i][0][2]) %= Mod;
}
cout << res <<"\n";
}
#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
int main () {
// file("teamwork");
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll num_Test = 1, dummy;
// cin >> dummy >> num_Test;
while(num_Test--)
solution();
}
/*
*/
Compilation message
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:98:22: warning: unused variable 'dummy' [-Wunused-variable]
98 | ll num_Test = 1, dummy;
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3416 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3932 KB |
Output is correct |
| 3 |
Correct |
1 ms |
3164 KB |
Output is correct |
| 4 |
Correct |
2 ms |
3932 KB |
Output is correct |
| 5 |
Correct |
2 ms |
3932 KB |
Output is correct |
| 6 |
Correct |
2 ms |
3932 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2908 KB |
Output is correct |
| 8 |
Correct |
2 ms |
3164 KB |
Output is correct |
| 9 |
Correct |
2 ms |
3676 KB |
Output is correct |
| 10 |
Correct |
2 ms |
3676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
