#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (int i = l; i < r; i++)
#define ForE(i, l, r) for (int i = l; i <= r; i++)
#define FordE(i, l, r) for (int i = l; i >= r; i--)
#define Fora(v, a) for (auto v: a)
#define bend(a) a.begin(), a.end()
#define isz(a) ((signed)a.size())
using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;
const int maxN = 2e3 + 5, mod = 1e9 + 7;
void sadd(int& x, int y){
if ((x += y) >= mod) x -= mod; return;
}
int add(int x, int y){
if ((x += y) >= mod) x -= mod; return x;
}
void ssub(int& x, int y){
if ((x -= y) < 0) x += mod; return;
}
int sub(int x, int y){
if ((x -= y) < 0) x += mod; return x;
}
int mul(int x, int y){
return 1ll * x * y % mod;
}
int binpow(int x, int y){
int ans = 1;
while (y){
if (y & 1) ans = mul(ans, x);
x = mul(x, x);
y >>= 1;
}
return ans;
}
int inv(int x){
return binpow(x, mod - 2);
}
#define div __div__
int div(int x, int y){
return mul(x, binpow(y, mod - 2));
}
int n, cs, cf;
int dp[maxN][maxN];
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("KEK.inp", "r", stdin);
// freopen("KEK.out", "w", stdout);
cin >> n >> cs >> cf;
dp[0][0] = 1;
int cap = 0;
ForE(i, 1, n){
ForE(cc, 1, n){
if (i == cs or i == cf){
sadd(dp[i][cc], dp[i - 1][cc - 1]);
sadd(dp[i][cc], dp[i - 1][cc]);
continue;
}
sadd(dp[i][cc], mul(dp[i - 1][cc - 1], cc - cap));
sadd(dp[i][cc], mul(dp[i - 1][cc + 1], cc));
}
if (i == cs or i == cf){
cap++;
}
}
cout << dp[n][1] << endl;
}
/*
==================================================+
INPUT: |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
OUTPUT: |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
*/
Compilation message
kangaroo.cpp: In function 'void sadd(int&, int)':
kangaroo.cpp:27:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
27 | if ((x += y) >= mod) x -= mod; return;
| ^~
kangaroo.cpp:27:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
27 | if ((x += y) >= mod) x -= mod; return;
| ^~~~~~
kangaroo.cpp: In function 'int add(int, int)':
kangaroo.cpp:31:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
31 | if ((x += y) >= mod) x -= mod; return x;
| ^~
kangaroo.cpp:31:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
31 | if ((x += y) >= mod) x -= mod; return x;
| ^~~~~~
kangaroo.cpp: In function 'void ssub(int&, int)':
kangaroo.cpp:35:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
35 | if ((x -= y) < 0) x += mod; return;
| ^~
kangaroo.cpp:35:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
35 | if ((x -= y) < 0) x += mod; return;
| ^~~~~~
kangaroo.cpp: In function 'int sub(int, int)':
kangaroo.cpp:39:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
39 | if ((x -= y) < 0) x += mod; return x;
| ^~
kangaroo.cpp:39:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
39 | if ((x -= y) < 0) x += mod; return x;
| ^~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
460 KB |
Output is correct |
5 |
Correct |
1 ms |
460 KB |
Output is correct |
6 |
Correct |
1 ms |
460 KB |
Output is correct |
7 |
Correct |
1 ms |
460 KB |
Output is correct |
8 |
Correct |
1 ms |
460 KB |
Output is correct |
9 |
Correct |
1 ms |
460 KB |
Output is correct |
10 |
Correct |
1 ms |
460 KB |
Output is correct |
11 |
Correct |
1 ms |
460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
460 KB |
Output is correct |
5 |
Correct |
1 ms |
460 KB |
Output is correct |
6 |
Correct |
1 ms |
460 KB |
Output is correct |
7 |
Correct |
1 ms |
460 KB |
Output is correct |
8 |
Correct |
1 ms |
460 KB |
Output is correct |
9 |
Correct |
1 ms |
460 KB |
Output is correct |
10 |
Correct |
1 ms |
460 KB |
Output is correct |
11 |
Correct |
1 ms |
460 KB |
Output is correct |
12 |
Correct |
1 ms |
1228 KB |
Output is correct |
13 |
Correct |
1 ms |
1088 KB |
Output is correct |
14 |
Correct |
2 ms |
1228 KB |
Output is correct |
15 |
Correct |
1 ms |
1228 KB |
Output is correct |
16 |
Correct |
1 ms |
1228 KB |
Output is correct |
17 |
Correct |
1 ms |
1228 KB |
Output is correct |
18 |
Correct |
1 ms |
1100 KB |
Output is correct |
19 |
Correct |
2 ms |
1224 KB |
Output is correct |
20 |
Correct |
1 ms |
1228 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
460 KB |
Output is correct |
5 |
Correct |
1 ms |
460 KB |
Output is correct |
6 |
Correct |
1 ms |
460 KB |
Output is correct |
7 |
Correct |
1 ms |
460 KB |
Output is correct |
8 |
Correct |
1 ms |
460 KB |
Output is correct |
9 |
Correct |
1 ms |
460 KB |
Output is correct |
10 |
Correct |
1 ms |
460 KB |
Output is correct |
11 |
Correct |
1 ms |
460 KB |
Output is correct |
12 |
Correct |
1 ms |
1228 KB |
Output is correct |
13 |
Correct |
1 ms |
1088 KB |
Output is correct |
14 |
Correct |
2 ms |
1228 KB |
Output is correct |
15 |
Correct |
1 ms |
1228 KB |
Output is correct |
16 |
Correct |
1 ms |
1228 KB |
Output is correct |
17 |
Correct |
1 ms |
1228 KB |
Output is correct |
18 |
Correct |
1 ms |
1100 KB |
Output is correct |
19 |
Correct |
2 ms |
1224 KB |
Output is correct |
20 |
Correct |
1 ms |
1228 KB |
Output is correct |
21 |
Correct |
6 ms |
4556 KB |
Output is correct |
22 |
Correct |
7 ms |
4940 KB |
Output is correct |
23 |
Correct |
7 ms |
5452 KB |
Output is correct |
24 |
Correct |
34 ms |
15888 KB |
Output is correct |
25 |
Correct |
35 ms |
15912 KB |
Output is correct |
26 |
Correct |
38 ms |
15908 KB |
Output is correct |
27 |
Correct |
33 ms |
15940 KB |
Output is correct |
28 |
Correct |
27 ms |
11976 KB |
Output is correct |