【传送门：】

---

简要题意：

　　求出$\sum_{i=1}^{n}i^{k}\mod p$

---

题解：

　　因为有多组数据，所以不能用差分表做

　　要用伯努利数来做（学了一上午。。）

　　伯努利数，$B_{0}=1$

　　因为$\sum_{j=0}^iC_{i+1}^jB_j=0$

　　所以$B_i=-\frac{1}{i+1}\sum_{j=0}^{i-1}C_{i+1}^{j}B_j$

　　预处理B数组

　　对于每个n,k，答案为$\sum_{i=1}^{n}i^k={1\over{k+1}}\sum_{i=1}^{k+1}C_{k+1}^i*B_{k+1-i}*(n+1)^i$

---

参考代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;typedef long long LL;LL Mod=1e9+7;LL ny[2100],jc[2100],B[2100];LL C(int n,int m){    return jc[n]*ny[m]%Mod*ny[n-m]%Mod;}LL p_mod(LL a,int b){    LL ans=1;    while(b!=0)    {        if(b%2==1) ans=ans*a%Mod;        a=a*a%Mod;b/=2;    }    return ans;}int main(){    ny[0]=1;jc[0]=1;    for(int i=1;i<=2000;i++) jc[i]=jc[i-1]*i%Mod,ny[i]=p_mod(jc[i],Mod-2);    B[0]=1;    for(int i=1;i<=2000;i++)    {        B[i]=0;        for(int j=0;j