blob: 250bf499018fb847c5bb1fea5d5db63a7665ff43 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
using ll = long long;
using ii = pair<int, int>;
constexpr int MX = 5005, MOD = 1e9+7;
inline ll pw(ll base, ll exp) {
ll res = 1;
while (exp) {
if (exp & 1) (res *= base) %= MOD;
exp >>= 1, (base *= base) %= MOD;
}
return res;
}
int inv[MX], pre[2][MX], DP[2][MX][MX];
int main() {
cin.tie(0)->sync_with_stdio(0);
int N, x; cin >> N >> x;
for (int i = 1; i <= N; ++i) inv[i] = pw(i, MOD-2);
for (int i = 0; i <= x; ++i) {
for (int j = 0; j <= N-x; ++j) {
DP[0][i][j] = (ll)(pre[0][i] + pre[1][j]) * inv[i + j] % MOD;
DP[1][i][j] = (ll)(pre[0][i] + pre[1][j] + i) * inv[i + j] % MOD;
(pre[0][i] += DP[1][i][j]) %= MOD;
(pre[1][j] += DP[0][i][j]) %= MOD;
}
}
ll ans = DP[0][x][N-x];
for (int i = 1; i <= N; ++i) (ans *= i) %= MOD;
cout << ans;
}
|
