This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ar array
#define sz(v) int(std::size(v))
using i64 = long long;
const int N = 3000;
const i64 MOD = 1e9 + 7;
int h, w;
int take[N + 1][N + 1];
i64 roll[N + 1];
i64 fac[N + 1], ifac[N + 1], p4[N + 1];
i64 inv(i64 a) {
return a == 1 ? 1 : inv(MOD % a) * (MOD - MOD / a) % MOD;
}
i64 nck(int n, int k) {
if (n < k || k < 0) return 0;
return fac[n] * ifac[k] % MOD * ifac[n - k] % MOD;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
roll[1] = 1;
for (int i = 3; i <= N; i += 2) roll[i] = roll[i - 2] * i % MOD;
fac[0] = ifac[0] = 1;
for (int i = 1; i <= N; i++) fac[i] = fac[i - 1] * i % MOD, ifac[i] = inv(fac[i]);
p4[0] = 1;
for (int i = 1; i <= N; i++) p4[i] = p4[i - 1] * 4 % MOD;
for (int k = 0; k <= N / 2; k++) for (int n = 0; n <= N; n++)
take[k][n] = nck(n, k * 2) * (!k ? 1 : roll[k * 2 - 1]) % MOD;
cin >> h >> w;
i64 ans = 0;
for (int x = 0; x <= w; x++) for (int y = 0; y <= h; y++) for (int z = 0; z <= min(w, h); z++) {
i64 num = nck(w, x) * take[x][h] % MOD
* nck(h - 2 * x, y) % MOD * take[y][w - x] % MOD
* fac[x] % MOD * fac[y] % MOD
* nck(w - x - 2 * y, z) % MOD * nck(h - 2 * x - y, z) % MOD * fac[z] % MOD * p4[z] % MOD;
ans = (ans + num) % MOD;
}
ans += MOD - 1;
ans %= MOD;
cout << ans << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |