# Solution

p[n,m]=∑i=1nf[i][m]=p[n2][m] ∑i=1n2f[i n2][m]” role=”presentation”>p[n,m]=∑ni=1f[i][m]=p[n2][m] ∑n2i=1f[i n2][m]p[n,m]=∑i=1nf[i][m]=p[n2][m] ∑i=1n2f[i n2][m]p[n,m]=\sum_{i=1}^{n}f[i][m]=p[\frac{n}{2}][m] \sum_{i=1}^{\frac{n}{2}}f[i \frac{n}{2}][m]
=∑i=1np[n2][m] ∑i=1n2∑j=1m−1f[i][j]∗f[n2][m−j]” role=”presentation”>            =∑ni=1p[n2][m] ∑n2i=1∑m−1j=1f[i][j]∗f[n2][m−j]            =∑i=1np[n2][m] ∑i=1n2∑j=1m−1f[i][j]∗f[n2][m−j]\ \ \ \ \ \ \ \ \ \ \ \ =\sum_{i=1}^{n}p[\frac{n}{2}][m] \sum_{i=1}^{\frac{n}{2}}\sum_{j=1}^{m-1}f[i][j]*f[\frac{n}{2}][m-j]
=∑i=1np[n2][m] ∑j=1m−1f[n2][m−j]∗∑i=1n2f[i][j]” role=”presentation”>            =∑ni=1p[n2][m] ∑m−1j=1f[n2][m−j]∗∑n2i=1f[i][j]            =∑i=1np[n2][m] ∑j=1m−1f[n2][m−j]∗∑i=1n2f[i][j]\ \ \ \ \ \ \ \ \ \ \ \ =\sum_{i=1}^{n}p[\frac{n}{2}][m] \sum_{j=1}^{m-1}f[\frac{n}{2}][m-j]*\sum_{i=1}^{\frac{n}{2}}f[i][j]
=∑i=1np[n2][m] ∑j=1m−1f[n2][m−j]∗p[n2][j]” role=”presentation”>            =∑ni=1p[n2][m] ∑m−1j=1f[n2][m−j]∗p[n2][j]            =∑i=1np[n2][m] ∑j=1m−1f[n2][m−j]∗p[n2][j]\ \ \ \ \ \ \ \ \ \ \ \ =\sum_{i=1}^{n}p[\frac{n}{2}][m] \sum_{j=1}^{m-1}f[\frac{n}{2}][m-j]*p[\frac{n}{2}][j]

# Code

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <complex>
#define rep(i,st,ed) for (int i=st;i<=ed;  i)
typedef std:: complex <double> com;
const double pi=acos(-1);
const double eps=0.1;
const int N=50005;
com a[N],b[N],c[N];
int g[N],f[N],p[N];
int rev[N],len,lg,MOD;
int A,B,C,n,m;
void FFT(com *a,int f) {
for (int i=0;i<len;i  ) if (i<rev[i]) std:: swap(a[i],a[rev[i]]);
for (int i=1;i<len;i<<=1) {
com wn(cos(pi/(double)i),(double)f*sin(pi/(double)i));
for (int j=0;j<len;j =i*2) {
com w(1,0);
for (int k=0;k<i;k  ) {
com u=a[j k],v=w*a[j k i];
a[j k]=u v; a[j k i]=u-v;
w*=wn;
}
}
}
if (f==-1) for (int i=0;i<len;i  ) a[i]/=len;
}
void solve1() {
rep(i,0,len-1) a[i]=f[i];
rep(i,0,len-1) b[i]=g[i];
FFT(a,1); FFT(b,1);
rep(i,0,len-1) c[i]=a[i]*b[i];
FFT(c,-1);
rep(i,1,m) f[i]=(int)(c[i].real() eps)%MOD,p[i]=(p[i] f[i])%MOD;
}
void solve2() {
rep(i,0,len-1) a[i]=f[i];
rep(i,0,len-1) b[i]=p[i];
FFT(a,1); FFT(b,1);
rep(i,0,len-1) c[i]=a[i]*b[i];
FFT(c,-1);
rep(i,1,m) p[i]=(p[i] (int)(c[i].real() eps)%MOD)%MOD;
rep(i,0,len-1) c[i]=a[i]*a[i];
FFT(c,-1);
rep(i,1,m) f[i]=(int)(c[i].real() eps)%MOD;
}
int main(void) {
freopen("data.in","r",stdin);
freopen("myp.out","w",stdout);
scanf("%d%d%d",&m,&MOD,&n);
scanf("%d%d%d",&A,&B,&C);
for (len=1,lg=0;len<=m*2;len*=2,lg  );
for (int i=0;i<len;i  ) rev[i]=(rev[i>>1]>>1)|((i&1)<<(lg-1));
rep(i,1,m) p[i]=g[i]=f[i]=(A%MOD*i%MOD*i%MOD B*i%MOD C)%MOD;
int now=0,w=1; n=tmp;
while (w*2<=n) w*=2,now  ;
while (now--) {
solve2();
if (n&(1<<now)) solve1();
}
printf("%d\n", p[m]);
return 0;
}