fft_pnt a[4096],z[4096]; ll@m++,@n++,@k[m]; rep(i,4096){ a[i].set(0,0); z[i].set(0,0); } rep(i,n){ ll@x; a[i].x=x; } z[0].x=m>2?powmod(a[0].x,sum[i,2,m](k[i]),1009):1; ll c=k[0]+(m>1?k[1]*1009:0); while(c){ fft(4096,a); if(c&1){ fft(4096,z); rep(i,4096){ z[i]*=a[i]; } fftinv(4096,z); rep(i,n){ z[i].set(fmod(floor(z[i].x/4096+.5),1009),0); } rep(i,n,4096){ z[i].set(0,0); } } c>>=1; rep(i,4096){ a[i]*=a[i]; } fftinv(4096,a); rep(i,n){ a[i].set(fmod(floor(a[i].x/4096+.5),1009),0); } rep(i,n,4096){ a[i].set(0,0); } } wt((ll)z(n).x);