#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007LL;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, cs, cf;
if (!(cin >> N >> cs >> cf)) return 0;
if (N == 2) {
cout << 1 << '\n';
return 0;
}
if (cs > cf) swap(cs, cf);
static long long dp[2001][2001];
for (int i = 0; i <= N; ++i)
for (int j = 0; j <= N; ++j)
dp[i][j] = 0;
dp[0][0] = 1;
for (int i = 1; i < cs; ++i) {
for (int c = 1; c <= i; ++c) {
dp[i][c] = (dp[i][c] + dp[i-1][c-1] * 1LL * c) % MOD;
}
for (int c = 0; c < i; ++c) {
dp[i][c] = (dp[i][c] + dp[i-1][c+1] * 1LL * c) % MOD;
}
}
if (cs >= 1) {
for (int c = 0; c <= N; ++c) {
long long val = dp[cs-1][c];
if (c > 0) val = (val + dp[cs-1][c-1]) % MOD;
dp[cs][c] = val;
}
}
for (int i = cs + 1; i < cf; ++i) {
for (int c = 1; c <= i; ++c) {
dp[i][c] = (dp[i][c] + dp[i-1][c-1] * 1LL * (c - 1)) % MOD;
}
for (int c = 0; c < i; ++c) {
dp[i][c] = (dp[i][c] + dp[i-1][c+1] * 1LL * c) % MOD;
}
}
for (int c = 0; c <= N; ++c) {
long long val = dp[cf-1][c];
if (c > 0) val = (val + dp[cf-1][c-1]) % MOD;
dp[cf][c] = val;
}
for (int i = cf + 1; i <= N; ++i) {
for (int c = 2; c <= i; ++c) {
dp[i][c] = (dp[i][c] + dp[i-1][c-1] * 1LL * (c - 2)) % MOD;
}
for (int c = 0; c < i; ++c) {
dp[i][c] = (dp[i][c] + dp[i-1][c+1] * 1LL * c) % MOD;
}
}
cout << dp[N][1] % MOD << '\n';
return 0;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |