求: 自然数幂和:
$$
\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):

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;
}