题目链接
题意；求$\sum_{i=1}^n i^kr^i$模$1e9 + 7$。($n, r \le 10^{18}$，$k \le 2000$)。

设$f(n, k) = \sum_{i=1}^n i^kr^i$。
$rf(n, k) = \sum_{i=1}^n i^kr^{i+1} = \sum_{i=2}^{n+1} (i-1)^kr^i$。
$f(n, k) - rf(n, k) = r - n^kr^{n+1} + \sum_{i=2}^n \Big (i^k - (i-1)^k \Big )r^i$。
$(1 -r)f(n, k) = r - n^kr^{n+1} - \sum_{i=2}^n\sum_{j=0}^{k-1} (-1)^{k-j} \big ( {k \atop j} \big ) i^jr^i$
$(1 - r)f(n, k) = r - n^kr^{n+1} - \sum_{j=0}^{k-1}(-1)^{k-j}\big ( {k \atop j} \big ) \sum_{i=2}^n i^jr^i$。
$f(n, k) = \frac{1}{1 - r}\Big (r - n^kr^{n+1} - \sum_{j=0}^{k-1}(-1)^{k-j}\big ( {k \atop j} \big ) (f(n, j) - r) \Big)$。
当$r > 1$的时候可以递推。$r = 1$需要特判，写一个自然数幂和。
复杂度$O(k^2)$。

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
71
72
73
74
75
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3000, mod = 1e9 + 7;
int t, f[maxn + 10], comb[maxn + 10][maxn + 10];
int inv[maxn + 10], ifac[maxn + 10];
int pre[maxn + 10], suf[maxn + 10];
int k, r;
ll n, tmpr;

inline int add(int x, int y) {
	x += y; return x < mod ? x : x - mod;
}
inline int dec(int x, int y) {
	x -= y; return x < 0 ? x + mod : x;
}
inline int mul(int x, int y) {
	return 1ll * x * y % mod;
}
int fpow(int x, ll y) {
	int ans = 1;
	while (y) {
		if (y & 1) ans = mul(ans, x);
		y >>= 1; x = mul(x, x);
	}
	return ans;
}

void init() {
	ifac[0] = 1;
	for (int i = 1; i <= maxn; ++i) {
		inv[i] = i == 1 ? 1 : dec(0, mul(mod / i, inv[mod % i]));
		ifac[i] = mul(ifac[i - 1], inv[i]);
	}
	for (int i = 0; i <= maxn; ++i) {
		comb[i][0] = 1;
		for (int j = 1; j <= i; ++j) comb[i][j] = add(comb[i - 1][j], comb[i - 1][j - 1]);
	}
}

int main() {
	init();
	scanf("%d", &t);
	while (t--) {
		scanf("%lld%d%lld", &n, &k, &tmpr);
		r = tmpr % mod;
		if (r == 1) {
			pre[0] = suf[k + 3] = 1;
			for (int i = 1; i <= k + 2; ++i)
				pre[i] = mul(pre[i - 1], dec(n % mod, i));
			for (int i = k + 2; i >= 1; --i)
				suf[i] = mul(suf[i + 1], dec(n % mod, i));
			int ans = 0;
			for (int i = 1, now = 0; i <= k + 2; ++i) {
				now = add(now, fpow(i, k));
				int w = mul(ifac[i - 1], ifac[k + 2 - i]);
				if ((k + 2 - i) & 1) w = dec(0, w);
				ans = add(ans, mul(mul(now, w), mul(pre[i - 1], suf[i + 1])));
			}
			printf("%d\n", ans);
		} else {
			f[0] = dec(mul(dec(fpow(r, n + 1), 1), fpow(dec(r, 1), mod - 2)), 1);
			for (int i = 1; i <= k; ++i) {
				f[i] = dec(r, mul(fpow(n % mod, i), fpow(r, n + 1)));
				for (int j = 0; j < i; ++j) {
					int w = mul(comb[i][j], dec(f[j], r));
					if ((i - j) & 1) f[i] = add(f[i], w);
					else f[i] = dec(f[i], w);
				}
				f[i] = mul(f[i], fpow(dec(1, r), mod - 2));
			}
			printf("%d\n", f[k]);
		}
	}
}