题意：给定 $n,k$，求 $\sum\limits^n_{i=1}\dbinom{n}{i}i^k\bmod(10^9+7)$。
$1\le n\le 10^9,1\le k\le 5000$。
很水的一道题。
根据第二类斯特林数的性质：
$$n^k=\sum^k_{i=1}\begin{Bmatrix}k\\i\end{Bmatrix}i!\dbinom{n}{i}$$
那么直接套进去：
$$\sum\limits^n_{i=1}\dbinom{n}{i}\sum^k_{j=1}\begin{Bmatrix}k\\j\end{Bmatrix}j!\dbinom{i}{j}$$
$$\sum^k_{j=1}\begin{Bmatrix}k\\j\end{Bmatrix}j!\sum\limits^n_{i=j}\dbinom{n}{i}\dbinom{i}{j}$$
$$\sum^k_{j=1}\begin{Bmatrix}k\\j\end{Bmatrix}j!\sum\limits^n_{i=j}\dfrac{n!}{i!(n-i)!}\dfrac{i!}{j!(i-j)!}$$
$$\sum^k_{j=1}\begin{Bmatrix}k\\j\end{Bmatrix}j!\sum\limits^n_{i=j}\dfrac{n!}{(n-i)!}\dfrac{1}{j!(i-j)!}$$
$$\sum^k_{j=1}\begin{Bmatrix}k\\j\end{Bmatrix}j!\sum\limits^n_{i=j}\dfrac{n!}{j!(n-j)!}\dfrac{(n-j)!}{(n-i)!(i-j)!}$$
$$\sum^k_{j=1}\begin{Bmatrix}k\\j\end{Bmatrix}j!\sum\limits^n_{i=j}\dbinom{n}{j}\dbinom{n-j}{i-j}$$
$$\sum^k_{j=1}\begin{Bmatrix}k\\j\end{Bmatrix}j!\dbinom{n}{j}\sum\limits^n_{i=j}\dbinom{n-j}{i-j}$$
$$\sum^k_{j=1}\begin{Bmatrix}k\\j\end{Bmatrix}j!\dbinom{n}{j}\sum\limits^{n-j}_{i=0}\dbinom{n-j}{i}$$
$$\sum^k_{j=1}\begin{Bmatrix}k\\j\end{Bmatrix}j!\dbinom{n}{j}2^{n-j}$$
如果我们知道了所有的 $\begin{Bmatrix}k\\j\end{Bmatrix}$ 那么这个式子可以做到 $O(k\log n)$。
而预处理这些斯特林数可以用 $k^2$ 递推，当然也可以用卷积做到 $k\log k$。
由于本题 $k^2$ 已经足够，而且模数不友好，直接递推就好了。
时间复杂度 $O(k^2+k\log n)$。
#include<bits/stdc++.h>
using namespace std;
const int mod=;
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline int read(){
int x=,f=;char ch=getchar();
while(ch<'' || ch>'') f|=ch=='-',ch=getchar();
while(ch>='' && ch<='') x=x*+ch-'',ch=getchar();
return f?-x:x;
}
int n,k,S[][];
inline int qpow(int a,int b){
int ans=;
for(;b;b>>=,a=1ll*a*a%mod) if(b&) ans=1ll*ans*a%mod;
return ans;
}
int main(){
n=read();k=read();
S[][]=;
FOR(i,,k) FOR(j,,i) S[i][j]=(S[i-][j-]+1ll*S[i-][j]*j)%mod;
int c=,f=,ans=;
FOR(i,,min(n,k)){
c=1ll*c*(n-i+)%mod*qpow(i,mod-)%mod;
f=1ll*f*i%mod;
ans=(ans+1ll*c*S[k][i]%mod*f%mod*qpow(,n-i))%mod;
}
printf("%d\n",ans);
}