题目分析
给定(n(nle10^9),k(kle 5000))，求：
[sumlimits_{i=0}^ninom{n}{i}cdot i^k
]
利用第二类斯特林数对(i^k)进行化简。
[egin{aligned}
ans&=sum_{i=0}^ninom{n}{i}i^k\
&=sum_{i=0}^ninom{n}{i}sum_{j=0}^iinom{i}{j}egin{Bmatrix}k\jend{Bmatrix}j!\
&=sum_{j=0}^nsum_{i=j}^ninom{n}{i}inom{i}{j}egin{Bmatrix}k\jend{Bmatrix}j!\
&=sum_{j=0}^ninom{n}{j}egin{Bmatrix}k\jend{Bmatrix}j!sum_{i=j}^ninom{n-j}{n-i}\
&=sum_{j=0}^ninom{n}{j}egin{Bmatrix}k\jend{Bmatrix}j!sum_{i=0}^{n-j}inom{n-j}{i}\
&=sum_{j=0}^ninom{n}{j}egin{Bmatrix}k\jend{Bmatrix}j!cdot2^{n-j}\
&=sum_{j=0}^kinom{n}{j}egin{Bmatrix}k\jend{Bmatrix}j!cdot2^{n-j}
end{aligned}
]
(O(k^2))递推或者(O(klogk))NTT算出斯特林数后，就可以直接计算答案了。