void f(ll n,double*a,double*r){ convolution(a,n,r,n,r,n); rep(i,n){ r[i]=fmod(floor(r[i]+.5),1009); } } { ll@m++,@n++,@k[m]; double@a[n]; double z[n]{1}; ll a0=a[0]; ll a1=n>1?a[1]:0; if(true){ ll c=k[0]; while(c){ if(c&1){ f(n,a,z); } c>>=1; f(n,a,a); } } if(m>1){ rep(i,n){ a[i]=0; } a[0]=a0; if(n>1009){ a[1009]=a1; } ll c=k[1]; while(c){ if(c&1){ f(n,a,z); } c>>=1; f(n,a,a); } } ll b=m>2?powmod(a0,sum[i,2,m](k[i]),1009):1; wt((ll)z(n)*b%1009); }