求: 自然数幂和: $$ \\sum\_{i = 1}^{n}i^k % mod $$ 一阶求和公式: $f(n) = n \* (n + 1) / 2$; 二阶求和公式: $f(n) = n \* (n + 1) \* (2 \* n + 1) / 6$; 三阶求和公式: $f(n) = n^2\*(n+1)^2/4$; k阶求和公式: 拉格朗日插值公式: $$ f(x)=\\sum\_{i=0}^{n} y\_{i} \\prod\_{j \\neq i} \\frac{x-x\_{j}}{x\_{i}-x\_{j}} $$ 拉格朗日插值: 通过n + 1个点确定唯一一个最大n次的多项式方程f(x), 使得这条曲线经过n + 1个点. 显然, k阶幂和公式是一个k + 1阶多项式, 所以我们需要k + 2个点, 往往这类题, k是很小的, 所以, 完全可以O(k), 暴力去算k + 2个点的值. 然后套公式. code模板(出处:[https://www.cnblogs.com/lfri/p/11556156.html](https://www.cnblogs.com/lfri/p/11556156.html)): 
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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll mod = 1e9 + 7;
const int maxk = 1000000 + 10;
ll n, k;

ll qpow(ll m, ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1)
            res = (res * m) % mod;
        m = (m * m) % mod;
        n = n >> 1;
    }
    return res;
}

ll fac[maxk], y[maxk];  //前k+2项前缀和都已经算好
ll Largrange() {
    fac[0] = fac[1] = 1, y[1] = 1;
    for (int i = 2; i <= k + 2; i++)
        fac[i] = fac[i - 1] * i % mod;      //预处理阶乘
    
    for (int i = 2; i <= k + 2; i++)
        y[i] = (y[i - 1] + qpow(i, k, mod)) % mod;  //预处理求出每一项的结果
    if (n <= k + 2)
        return y[n];

    ll ans = 0, prod = 1, sig;
    
    for (ll i = n - k - 2; i <= n - 1; i++)
        prod = prod * i % mod;
    
    for (ll i = 1; i <= k + 2; i++) {
        ll fz = prod * qpow(n - i, mod - 2, mod) % mod;
        ll fm = qpow(fac[i - 1] * fac[k + 2 - i] % mod, mod - 2, mod);
        
        if ((k + 2 - i) % 2 == 0)
            sig = 1;
        else
            sig = -1;
        ans = (ans + sig * y[i] * fz % mod * fm % mod + 2 * mod) % mod;
    }
    return ans;
}


int main() {
    scanf("%lld%lld", &n, &k);
    printf("%lld\n", Largrange());

    return 0;
}