思路
首先发现 \(\sum_{i = 1}^{n}i^k\) 是一个 \(k + 1\) 次多项式，那么我们需要求出 \(k + 2\) 个点才能得到唯一的一个 \(f(t) = \sum_{i = 1}^{t}{i^k}\)。
不难通过拉格朗日插值法，将 \(x = 1 \sim (k + 2)\) 的情况一一带入：
\[f(n) = \sum_{i = 1}^{k + 2}{((\sum_{j = 1}^{i}j^k) \times (\prod_{i \neq j}{\frac{n - x_j}{x_i - x_j}}))} \]但是，普通的拉格朗日插值法是 \(\Theta(k^2)\)，于是我们需要发掘本题中的特殊性。
可以轻易将原式转化为：
\[f(n) = \sum_{i = 1}^{k + 2}{((\sum_{j = 1}^{i}j^k) \times \frac{\prod_{i \neq j}{(n - x_j)}}{\prod_{i \neq j}{(x_i - x_j)}})} \]发现 \(x \in [1,k + 2]\)，那么容易转化：
\[f(n) = \sum_{i = 1}^{k + 2}{((\sum_{j = 1}^{i}j^k) \times \frac{\prod_{i \neq j}{(n - j)}}{\prod_{i \neq j}{(i - j)}})} \]然后你对于 \(\prod\) 里面分数的分子、分母分别计算。
对于分子：
\[\prod_{i \neq j}{(n - x_j)} = \frac{\prod_{j = 1}^{k + 2}(n - j)}{n - i} \]然后处理出 \(\prod_{j = 1}^{k + 2}(n - j)\) 即可。
对于分母：
\[\prod_{i \neq j}{(i - j)} = (\prod_{j = 1}^{i - 1}{j}) \times (\prod_{j = -1}^{i - k - 2}{j}) \]定义 \(g(i) = (\prod_{j = 1}^{i - 1}{j}) \times (\prod_{j = -1}^{i - k - 2}{j})\)，考虑 \(g(i)\) 与 \(g(i - 1)\) 的关系。
发现前一个 \(\prod\) 中 \(g(i)\) 比 \(g(i - 1)\) 多乘以一个 \(i - 1\)，后一个 \(\prod\) 中 \(g(i)\) 比 \(g(i - 1)\) 少乘一个 \(i - k - 3\)。
因此 \(g(i) = g(i - 1) \times \frac{i - 1}{i - k - 3}\)。特别的 \(g(1) = \prod_{j = -1}^{-k - 1}j\)
将分子、分母代入原式即可。
观察到当 \(k + 2 \geq n\) 时，\(n - i\) 会被减成 \(0\)，因此需要暴力 \(\Theta(n)\) 计算。
Code
#include <bits/stdc++.h>
#define re register
#define int long long
#define Add(a,b) ((((a) % mod + (b) % mod) % mod + mod) % mod)
#define Mul(a,b) ((((a) % mod) * ((b) % mod) % mod + mod) % mod)
#define Div(a,b) (Mul(a,qmi(((b) % mod + mod) % mod,mod - 2)))
using namespace std;
const int mod = 1e9 + 7;
int n,k,ans;
int mul = 1,g = 1,y;
inline int read(){
int r = 0,w = 1;
char c = getchar();
while (c < '0' || c > '9'){
if (c == '-') w = -1;
c = getchar();
}
while (c >= '0' && c <= '9'){
r = (r << 3) + (r << 1) + (c ^ 48);
c = getchar();
}
return r * w;
}
inline int qmi(int a,int b){
int res = 1;
while (b){
if (b & 1) res = Mul(res,a);
a = Mul(a,a),b >>= 1;
}
return res;
}
inline void solve1(){
for (re int i = 1;i <= n;i++) ans = Add(ans,qmi(i,k));
}
inline void solve2(){
for (re int i = 1;i <= k + 2;i++) mul = Mul(mul,n - i);
for (re int i = 1;i <= k + 2;i++){
y = Add(y,qmi(i,k));
if (i == 1){
for (re int j = -1;j >= -k - 1;j--) g = Mul(g,j);
}
else g = Mul(g,Div(i - 1,i - k - 3));
int a = Div(mul,n - i);
ans = Add(ans,Mul(y,Div(a,g)));
}
}
signed main(){
n = read(),k = read();
if (k + 2 >= n) solve1();
else solve2();
printf("%lld",ans);
return 0;
}