#include <bits/stdc++.h>
#define int long long
using namespace std;
string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
bool first = true;
string res = "[";
for (const auto &x : v) {
if (!first)
res += ", ";
first = false;
res += to_string(x);
}
res += "]";
return res;
}
void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
cout << ' ' << to_string(H);
dbg_out(T...);
}
#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
const int MOD = 1e9 + 7;
int add(int x, int y) {
x += y;
if (x >= MOD)
x -= MOD;
return x;
}
int sub(int x, int y) {
x -= y;
if (x < 0)
x += MOD;
return x;
}
int mult(int a, int b) { return a * b % MOD; }
int fastpow(int a, int b) {
int ret = 1;
for (; b; b /= 2, a = mult(a, a))
if (b % 2)
ret = mult(a, ret);
return ret;
}
const int MAXN = 1e5 + 1;
int fact[MAXN], invFact[MAXN];
void initFact() {
fact[0] = 1;
for (int i = 1; i < MAXN; ++i)
fact[i] = mult(i, fact[i - 1]);
invFact[MAXN - 1] = fastpow(fact[MAXN - 1], MOD - 2);
for (int i = MAXN - 1; i; --i)
invFact[i - 1] = mult(i, invFact[i]);
}
int binom(int n, int k) {
if (k < 0 or k > n)
return 0;
return mult(fact[n], mult(invFact[k], invFact[n - k]));
}
signed main(void) {
ios_base::sync_with_stdio(false);
cin.tie(0);
initFact();
int N, K;
cin >> N >> K;
K = N - K;
int ret = 0;
for (int j = 0; j <= K; ++j) {
int toAdd = mult(binom(N + 1, j), fastpow(K + 1 - j, N));
if (j % 2)
ret = sub(ret, toAdd);
else
ret = add(ret, toAdd);
}
cout << ret << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1876 KB |
Output is correct |
2 |
Correct |
2 ms |
1892 KB |
Output is correct |
3 |
Correct |
2 ms |
1876 KB |
Output is correct |
4 |
Correct |
2 ms |
1896 KB |
Output is correct |
5 |
Correct |
2 ms |
1876 KB |
Output is correct |
6 |
Correct |
2 ms |
1876 KB |
Output is correct |
7 |
Correct |
3 ms |
1876 KB |
Output is correct |
8 |
Correct |
2 ms |
1892 KB |
Output is correct |
9 |
Correct |
2 ms |
1888 KB |
Output is correct |
10 |
Correct |
2 ms |
1876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1876 KB |
Output is correct |
2 |
Correct |
2 ms |
1892 KB |
Output is correct |
3 |
Correct |
2 ms |
1876 KB |
Output is correct |
4 |
Correct |
2 ms |
1896 KB |
Output is correct |
5 |
Correct |
2 ms |
1876 KB |
Output is correct |
6 |
Correct |
2 ms |
1876 KB |
Output is correct |
7 |
Correct |
3 ms |
1876 KB |
Output is correct |
8 |
Correct |
2 ms |
1892 KB |
Output is correct |
9 |
Correct |
2 ms |
1888 KB |
Output is correct |
10 |
Correct |
2 ms |
1876 KB |
Output is correct |
11 |
Correct |
2 ms |
1876 KB |
Output is correct |
12 |
Correct |
2 ms |
1876 KB |
Output is correct |
13 |
Correct |
2 ms |
1876 KB |
Output is correct |
14 |
Correct |
2 ms |
1876 KB |
Output is correct |
15 |
Correct |
2 ms |
1876 KB |
Output is correct |
16 |
Correct |
2 ms |
1876 KB |
Output is correct |
17 |
Correct |
2 ms |
1876 KB |
Output is correct |
18 |
Correct |
2 ms |
1876 KB |
Output is correct |
19 |
Correct |
2 ms |
1888 KB |
Output is correct |
20 |
Correct |
2 ms |
1876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1876 KB |
Output is correct |
2 |
Correct |
2 ms |
1892 KB |
Output is correct |
3 |
Correct |
2 ms |
1876 KB |
Output is correct |
4 |
Correct |
2 ms |
1896 KB |
Output is correct |
5 |
Correct |
2 ms |
1876 KB |
Output is correct |
6 |
Correct |
2 ms |
1876 KB |
Output is correct |
7 |
Correct |
3 ms |
1876 KB |
Output is correct |
8 |
Correct |
2 ms |
1892 KB |
Output is correct |
9 |
Correct |
2 ms |
1888 KB |
Output is correct |
10 |
Correct |
2 ms |
1876 KB |
Output is correct |
11 |
Correct |
2 ms |
1876 KB |
Output is correct |
12 |
Correct |
2 ms |
1876 KB |
Output is correct |
13 |
Correct |
2 ms |
1876 KB |
Output is correct |
14 |
Correct |
2 ms |
1876 KB |
Output is correct |
15 |
Correct |
2 ms |
1876 KB |
Output is correct |
16 |
Correct |
2 ms |
1876 KB |
Output is correct |
17 |
Correct |
2 ms |
1876 KB |
Output is correct |
18 |
Correct |
2 ms |
1876 KB |
Output is correct |
19 |
Correct |
2 ms |
1888 KB |
Output is correct |
20 |
Correct |
2 ms |
1876 KB |
Output is correct |
21 |
Correct |
2 ms |
1892 KB |
Output is correct |
22 |
Correct |
2 ms |
1876 KB |
Output is correct |
23 |
Correct |
2 ms |
1892 KB |
Output is correct |
24 |
Correct |
2 ms |
1828 KB |
Output is correct |
25 |
Correct |
2 ms |
1876 KB |
Output is correct |
26 |
Correct |
2 ms |
1876 KB |
Output is correct |
27 |
Correct |
2 ms |
1876 KB |
Output is correct |
28 |
Correct |
2 ms |
1876 KB |
Output is correct |
29 |
Correct |
2 ms |
1876 KB |
Output is correct |
30 |
Correct |
2 ms |
1876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1876 KB |
Output is correct |
2 |
Correct |
2 ms |
1892 KB |
Output is correct |
3 |
Correct |
2 ms |
1876 KB |
Output is correct |
4 |
Correct |
2 ms |
1896 KB |
Output is correct |
5 |
Correct |
2 ms |
1876 KB |
Output is correct |
6 |
Correct |
2 ms |
1876 KB |
Output is correct |
7 |
Correct |
3 ms |
1876 KB |
Output is correct |
8 |
Correct |
2 ms |
1892 KB |
Output is correct |
9 |
Correct |
2 ms |
1888 KB |
Output is correct |
10 |
Correct |
2 ms |
1876 KB |
Output is correct |
11 |
Correct |
2 ms |
1876 KB |
Output is correct |
12 |
Correct |
2 ms |
1876 KB |
Output is correct |
13 |
Correct |
2 ms |
1876 KB |
Output is correct |
14 |
Correct |
2 ms |
1876 KB |
Output is correct |
15 |
Correct |
2 ms |
1876 KB |
Output is correct |
16 |
Correct |
2 ms |
1876 KB |
Output is correct |
17 |
Correct |
2 ms |
1876 KB |
Output is correct |
18 |
Correct |
2 ms |
1876 KB |
Output is correct |
19 |
Correct |
2 ms |
1888 KB |
Output is correct |
20 |
Correct |
2 ms |
1876 KB |
Output is correct |
21 |
Correct |
2 ms |
1892 KB |
Output is correct |
22 |
Correct |
2 ms |
1876 KB |
Output is correct |
23 |
Correct |
2 ms |
1892 KB |
Output is correct |
24 |
Correct |
2 ms |
1828 KB |
Output is correct |
25 |
Correct |
2 ms |
1876 KB |
Output is correct |
26 |
Correct |
2 ms |
1876 KB |
Output is correct |
27 |
Correct |
2 ms |
1876 KB |
Output is correct |
28 |
Correct |
2 ms |
1876 KB |
Output is correct |
29 |
Correct |
2 ms |
1876 KB |
Output is correct |
30 |
Correct |
2 ms |
1876 KB |
Output is correct |
31 |
Incorrect |
9 ms |
1876 KB |
Output isn't correct |
32 |
Halted |
0 ms |
0 KB |
- |