#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(),v.end()
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 = 2e3 + 7;
const int Mod = 1e9 + 7;
const int INF = 1e9 + 7;
const ll BASE = 137;
int n, m;
int h[N];
ll dp[N][N];
ll fac[2 * N];
int pre[N];
ll power (int n, int m) {
if (m == 0) return 1;
ll t = power (n, m >> 1);
(t *= t) %= Mod;
if (m & 1) return n * t % Mod;
else return t;
}
ll C (int r, int n) {
if (r > n) return 0;
return fac[n] * power (fac[r], Mod - 2) % Mod * power (fac[n - r], Mod - 2) % Mod;
}
void solution () {
fac[0] = 1;
rep (i, 1, 2 * n) fac[i] = fac[i - 1] * i % Mod;
cin >> n >> m;
rep (i, 0, 2 * n - 1) {
h[i % m + 1]++;
}
// vector<pair<int,int>> vec;
// rep (j, 0, 1)
// rep (i, 1, n) vec.push_back({i, j});
// sort (ALL(vec));
// ll res = 0;
// do {
// int ok = 1;
// rep (i, 0, 2 * n - 1) if (i >= m && vec[i].fs == vec[i - m].fs) ok = 0;
// res += ok;
// if (ok) {
// iter (&id, vec) cout << id.fs<<","<<id.se <<" ";
// cout<<"\n";
// }
// }while(next_permutation(ALL(vec)));
// cout << res <<"\n";
rep (i, 1, m) {
pre[i] = pre[i - 1] + h[i];
// cout << h[i] <<" ";
}
// cout<<"\n";
dp[1][h[1]] = C(h[1], n) * fac[h[1]] % Mod * power(2, h[1]) % Mod;
// cout <<h[1] <<" "<<dp[1][h[1]] <<"\n";
rep (i, 1, m)
rep (j, 0, 2 * n) {
rep (x, 0, h[i]) {
int nj = j + 2 * x - h[i + 1];
if (nj >= 0 && nj <= 2 * n) {
int pcol = nj + (pre[i + 1] - nj) / 2;
int remcol = n - (pcol - x);
(dp[i + 1][nj] += dp[i][j] * C(h[i + 1] - x, j) % Mod * C (x, h[i + 1]) % Mod * C(x, remcol) % Mod * fac[x] % Mod * fac[h[i + 1] - x] * power(2, x) % Mod) %= Mod;
// if (nj == 2) cout << x <<" "<<nj<<" "<<remcol<<" aaa\n";
}
// if (j == 2 && x == 0) cout << dp[i - 1][j] <<"hihi "<<dp[i][j + 2 * x - h[i]]<<"\n";
}
// cout << i<<","<<j<<" "<<dp[i][j] <<"\n";
}
// cout << dp[2][2] <<"\n";
// return;
cout << dp[m][0] <<"\n";
}
#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
// file("c");
ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
int num_Test = 1;
// cin >> num_Test;
while (num_Test--)
solution();
}
/*
no bug challenge +2
2 + 8 * 2 - 9
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
