题目分析

给定(n(nle10^9),k(kle 5000))，求：
[ sumlimits_{i=0}^nbinom{n}{i}cdot i^k ]

利用第二类斯特林数对(i^k)进行化简。
[ begin{aligned} ans&=sum_{i=0}^nbinom{n}{i}i^k&;=sum_{i=0}^nbinom{n}{i}sum_{j=0}^ibinom{i}{j}begin{Bmatrix}kjend{Bmatrix}j!&;=sum_{j=0}^nsum_{i=j}^nbinom{n}{i}binom{i}{j}begin{Bmatrix}kjend{Bmatrix}j!&;=sum_{j=0}^nbinom{n}{j}begin{Bmatrix}kjend{Bmatrix}j!sum_{i=j}^nbinom{n-j}{n-i}&;=sum_{j=0}^nbinom{n}{j}begin{Bmatrix}kjend{Bmatrix}j!sum_{i=0}^{n-j}binom{n-j}{i}&;=sum_{j=0}^nbinom{n}{j}begin{Bmatrix}kjend{Bmatrix}j!cdot2^{n-j}&;=sum_{j=0}^kbinom{n}{j}begin{Bmatrix}kjend{Bmatrix}j!cdot2^{n-j} end{aligned} ]

(O(k^2)?)递推或者(O(klogk)?)NTT算出斯特林数后，就可以直接计算答案了。