记录编号	571009	评测结果	AAAAAAAAAA
题目名称	[CF622F] The Sum of the k-th Powers	最终得分	100
用户昵称	lihaoze	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2022-05-02 08:18:17	内存使用	0.00 MiB

#include <bits/stdc++.h>
#define OPEN(_x) freopen(#_x".in", "r", stdin); freopen(#_x".out", "w", stdout)
#define rep(_x, _y, _z) for (int _x = (_y); _x <= (_z); ++ _x)
#define rep1(_x, _y, _z) for (int _x = (_y); _x < (_z); ++ _x)
#define fi first
#define se second

using i64 = long long;
using PII = std::pair<int, int>;

const int N = 1e6+10, MOD = 1e9+7;

i64 powM(i64 a, i64 t) {
	i64 ret = 1;
	for (; t; t >>= 1, a *= a) if (t & 1) ret *= ret * a % MOD;
	return ret;
}

i64 n, m, res, y[N], lf[N], rf[N], ifac[N];

int main() {
	OPEN(powsum);
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cin >> n >> m;
	rep (i, 1, m + 2) y[i] = (y[i - 1] + powM(i, m)) % MOD;
	m += 2;
	ifac[0] = ifac[1] = 1;
	rep (i, 2, m) ifac[i] = ifac[MOD % i] * (MOD - MOD / i) % MOD;
	rep (i, 2, m) ifac[i] = ifac[i] * ifac[i - 1] % MOD;
	lf[0] = 1;
	rep (i, 1, m) lf[i] = lf[i - 1] * (n - i) % MOD;
	rf[m + 1] = 1;
	for (int i = m; i; -- i) rf[i] = rf[i + 1] * (n - i) % MOD;
	rep (i, 1, m) res = (res + y[i] * lf[i - 1] % MOD *
						 rf[i + 1] % MOD * ifac[i - 1] % MOD *
						 ((m - i) & 1 ? MOD - ifac[m - i] : ifac[m - i])) % MOD;
	std::cout << (res + MOD) % MOD;
	return 0;
}