我的方案:时间复杂度O(k^2)
#include <bits/stdc++.h>
using namespace std;
#define m 10007
const int N = 2005;
long long c[N][N], bfs[N], inv[N], it[N];
long long n, ans, sum = 0;
int k, i, j;
int main()
{
scanf("%lld %d", &n, &k);
n %= m;
for(c[0][0] = i = 1; i < N; i++)
for(c[i][0] = c[i][i] = j = 1; j < i; j++)
c[i][j] = (c[i-1][j] % m + c[i-1][j-1] % m) % m;
for(inv[1] = 1, i = 2; i < N; i++)
inv[i] = (m - m / i) * inv[m % i] % m;
for(bfs[0] = i = 1; i < N - 1; i++)
{
ans = 0;
for(int j = 0; j < i; j++)
ans = (ans + c[i+1][j] * bfs[j]) % m;
bfs[i] = ((ans * -inv[i+1]) % m + m) % m;
}
for(it[0] = i = 1; i < N; i++)
it[i] = it[i - 1] * (n + 1) % m;
for(i = 1; i <= k + 1; i++)
sum = (sum + c[k+1][i] * it[i] % m * bfs[k+1-i] % m) % m;
printf("%lld\n", (inv[k + 1] * sum) % m);
return 0;
}