题目描述：求
\[\sum_{i=1}^ni^kr^i
\]
\]
对某个质数取模。\(T\)组数据。
数据范围：\(n,r\le 10^{18},\sum k\le 2.56\times 10^6\)
数论神题。。。
我们设\(S_k(n)=\sum_{i=1}^{n-1}i^kr^i\)，通过推通项公式，你会发现这个结论：
\[S_k(n)=r^nF_k(n)-F_k(0)
\]
\]
其中\(F_k(n)\)是一个关于\(n\)且次数不高于\(k\)的多项式。
如何证明呢？首先你可以通过错位相减法得到一个递推公式，然后就可以数学归纳法了。
然后我们就是要求出\(F_k(0),F_k(1),F_k(2),\ldots,F_k(k+1)\)，这样就可以通过拉格朗日插值求出\(F_k(n)\)。
我们注意到\(S_k(n)-S_k(n-1)=r^nF_k(n)-r^{n-1}F_k(n-1)=r^{n-1}(n-1)^k\)，所以\(F_k(n)=\dfrac{F_k(n-1)+(n-1)^k}{r}\)。
然后我们知道，\(k\)次多项式的\(k+1\)阶差分为\(0\)，即
\[\sum_{i=0}^{k+1}(-1)^i\binom{k+1}{i}F_k(k+1-i)=0
\]
\]
于是可以设\(F_k(0)=x\)，然后不停代入，然后用这个式子解方程。具体实现可以写一个二项式binom来做。
注意特判一些特殊情况。时间复杂度\(O(k)\)。