题目分析
一眼看上去就像是一个模拟题目，但是(n)的范围过大。
冷静分析一下发现难点在于如何快速求出幂和。
考虑使用伯努利数。
(B_0=1)
(B_n=-frac{1}{n+1}sumlimits_{i=0}^{n-1}inom{n+1}{i}* B_i)
(sumlimits_{i=1}^ni^k=frac{1}{k+1}* sumlimits_{i=1}^{k+1} inom{k+1}{i}* B_{k-i+1}* (n+1)^i)
一眼看上去就像是一个模拟题目，但是(n)的范围过大。
冷静分析一下发现难点在于如何快速求出幂和。
考虑使用伯努利数。
(B_0=1)
(B_n=-frac{1}{n+1}sumlimits_{i=0}^{n-1}inom{n+1}{i}* B_i)
(sumlimits_{i=1}^ni^k=frac{1}{k+1}* sumlimits_{i=1}^{k+1} inom{k+1}{i}* B_{k-i+1}* (n+1)^i)