还好有题解，公式不用自己推了
#include<bits/stdc++.h>
using namespace std;
const int _G=3,mod=1004535809,Maxn=135000,MaxNum=10000500;
long long powM(long long a,int t=mod-2) {
long long ans=1;
while(t) {
if(t&1)ans=ans*a%mod;
a=a*a%mod;
t>>=1;
}
return ans;
}
const int invG=powM(_G);
int tr[Maxn<<1];
void NTT(int *g,bool op,int n) {
static unsigned long long f[Maxn<<1],w[Maxn]= {1};
for(int i=0; i<n; i++)f[i]=g[tr[i]];
for(int l=1; l<n; l<<=1) {
unsigned long long tG=powM(op?_G:invG,(mod-1)/(l+l));
for(int i=1; i<l; i++)w[i]=w[i-1]*tG%mod;
for(int k=0; k<n; k+=l+l)
for(int p=0; p<l; p++) {
int tt=w[p]*f[k|l|p]%mod;
f[k|l|p]=f[k|p]+mod-tt;
f[k|p]+=tt;
}
if(l==(1<<10))for(int i=0; i<n; i++)f[i]%=mod;
}
if(!op) {
unsigned long long invn=powM(n);
for(int i=0; i<n; ++i)
g[i]=f[i]%mod*invn%mod;
} else for(int i=0; i<n; ++i)g[i]=f[i]%mod;
}
int n,m,S,lim,limNum;
long long w[Maxn],fac[MaxNum],ifac[MaxNum];
void Init() {
limNum=max(n,m);
fac[0]=1;
for(int i=1; i<=limNum; i++)fac[i]=fac[i-1]*i%mod;
ifac[limNum]=powM(fac[limNum]);
for(int i=limNum; i; i--)ifac[i-1]=ifac[i]*i%mod;
}
long long C(int n,int m) {
return fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
inline long long clacF(int x) {
return C(m,x)*fac[n]%mod*powM(ifac[S],x)%mod*ifac[n-S*x]%mod*powM(m-x,n-S*x)%mod;
}
int A[Maxn<<1],B[Maxn<<1];
int main() {
scanf("%d%d%d",&n,&m,&S);
lim=min(m,n/S);
Init();
for(int i=0; i<=lim; i++) {
A[i]=clacF(i)*fac[i]%mod;
B[i]=(i&1) ? mod-ifac[i] : ifac[i];
}
reverse(A,A+lim+1);
for(n=1; n<lim+lim+2; n<<=1);
for(int i=0; i<n; i++)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
NTT(A,1,n);
NTT(B,1,n);
for(int i=0; i<n; i++)A[i]=1ll*A[i]*B[i]%mod;
NTT(A,0,n);
reverse(A,A+lim+1);
long long ans=0;
for(int i=0,w; i<=lim; i++) {
scanf("%d",&w);
ans=(ans+A[i]*ifac[i]%mod*w)%mod;
}
printf("%lld",ans);
return 0;
}