题面
题解
这种颓柿子的题我可能死活做不出来……
首先(r=0)……算了不说了，(r=1)就是个裸的自然数幂次和直接爱怎么搞怎么搞了，所以以下都假设(r>1)
设
[s_p=sum_{i=1}^n i^pr^i
]
我们要求的就是(s_k)
因为有
[s_k=sum_{i=1}^n i^kr^i
]
[rs_k=sum_{i=2}^{n+1}r^{i}(i-1)^k
]
两个柿子减一减
[(r-1)s_k=r^{n+1}n^k-r+sum_{i=2}^nr^ileft((i-1)^k-i^k
ight)
]
然后来考虑后面这个东西
[egin{aligned}
sum_{i=2}^nr^ileft((i-1)^k-i^k
ight)
&=sum_{i=2}^nr^ileft(sum_{j=0}^k{kchoose j}i^j(-1)^{k-j}-i^k
ight)\
&=sum_{i=2}^nr^isum_{j=0}^{k-1}{kchoose j}i^j(-1)^{k-j}\
&=sum_{j=0}^{k-1}{kchoose j}(-1)^{k-j}sum_{i=2}^nr^ii^j\
&=sum_{j=0}^{k-1}{kchoose j}(-1)^{k-j}left(s(j)-r
ight)\
end{aligned}
]
那么就可以(O(k^2))递推了
//minamoto
#include<bits/stdc++.h>
#define R register
#define ll long long
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
using namespace std;
const int N=2005,P=1e9+7;
inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}
inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}
inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}
int ksm(R int x,R ll y){
R int res=1;
for(;y;y>>=1,x=mul(x,x))if(y&1)res=mul(res,x);
return res;
}
int fac[N],ifac[N],inv[N],Pre[N],suf[N],f[N],s[N];
ll n,r;int k,m;
inline int C(R int n,R int m){return 1ll*fac[n]*ifac[m]%P*ifac[n-m]%P;}
void init(int n=N-1){
inv[0]=inv[1]=ifac[0]=ifac[1]=fac[0]=fac[1]=1;
fp(i,2,n){
fac[i]=mul(fac[i-1],i),
inv[i]=mul(P-P/i,inv[P%i]),
ifac[i]=mul(ifac[i-1],inv[i]);
}
}
int Lagrange(){
n%=P;
fp(i,1,k+2)f[i]=add(f[i-1],ksm(i,k));
if(n<=k+2)return f[n];
m=k+2;
Pre[0]=1;fp(i,1,m)Pre[i]=mul(Pre[i-1],n-i);
suf[m+1]=1;fd(i,m,1)suf[i]=mul(suf[i+1],n-i);
int res=0,ty=(m-1)&1?P-1:1;
fp(i,1,m)res=add(res,1ll*f[i]*ty%P*Pre[i-1]%P*suf[i+1]%P*ifac[m-i]%P*ifac[i-1]%P),ty=P-ty;
return res;
}
int calc(){
if(!r)return 0;
R int p=ksm(r,n+1),q=1,invr=ksm(r-1,P-2),ty;
s[0]=mul(dec(p,r),invr),n%=P;
fp(i,1,k){
q=mul(q,n),s[i]=dec(mul(p,q),r),ty=(i&1)?P-1:1;
fp(j,0,i-1)s[i]=add(s[i],1ll*C(i,j)*ty%P*dec(s[j],r)%P),ty=P-ty;
s[i]=mul(s[i],invr);
}
return s[k];
}
int main(){
// freopen("testdata.in","r",stdin);
init();
int T;scanf("%lld",&T);
while(T--){
scanf("%lld%d%lld
",&n,&k,&r),r%=P;
printf("%d
",r==1?Lagrange():calc());
}
return 0;
}