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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| #include<bits/stdc++.h>
#define LL long long
using namespace std;
template <class T>
inline void read(T &res)
{
res = 0; bool flag = 0;
char c = getchar();
while(c < '0' || c > '9') { if(c == '-') flag = 1; c = getchar(); }
while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
if(flag) res = -res;
}
template <class T, class ...ARC>
inline void read(T &res, ARC &...com){ read(res), read(com...); }
template <class T>
inline void out(T res)
{
if(res < 0) putchar('-'), res = -res;
if(res > 10) out(res / 10);
putchar(res % 10 + '0');
}
template <class T>
inline void write(T res)
{
out(res), putchar('\n');
}
const int N = 1e6 + 100, mod = 1e9 + 7;
int n, k;
inline int qpow(int x, int k)
{
int res = 1;
while(k)
{
if(k & 1) res = 1ll * res * x % mod;
k >>= 1;
x = 1ll * x * x % mod;
}
return res;
}
int fac[N], inv1[N], inv2[N];
inline void init()
{
for(int i = 1;i <= k + 2;i ++) fac[i] = qpow(i, k);
for(int i = 1;i <= k + 2;i ++) fac[i] = (fac[i] + fac[i - 1]) % mod;
inv1[0] = 1;
for(int i = 1;i <= k + 2;i ++) inv1[i] = 1ll * inv1[i - 1] * qpow(i, mod - 2) % mod;
}
int ans = 1, pw[N], pw1[N];
inline int calc(int x)
{
ans = 0;
pw[0] = 1;
for(int i = 1;i <= k + 2;i ++) pw[i] = 1ll * pw[i - 1] * (x - i) % mod;
pw1[k + 3] = 1;
for(int i = k + 2;i >= 0;i --) pw1[i] = 1ll * pw1[i + 1] * (x - i) % mod;
for(int i = 1, o, u;i <= k + 2;i ++)
{
o = 1ll * inv1[i - 1] % mod * inv1[k + 2 - i] * ((k - i) & 1 ? -1 : 1) % mod;
u = 1ll * pw[i - 1] % mod * pw1[i + 1] % mod;
ans = (ans + 1ll * fac[i] % mod * o % mod * u % mod) % mod;
}
return (ans % mod + mod) % mod;
}
int main()
{
read(n, k);
init();
cout << calc(n) << endl;
return 0;
}
|