const ll mod = 998244353, G = 3, invg = 332748118; int N, m, lim, l, rev[100005], tot; ll dp[100005], sum[100005], F[100005], tmp[100005], invn, O, S, U, p; ll aa[100005], bb[100005];
inline ll fpow(ll x, ll t){ ll ret = 1; for (; t; t >>= 1, x = x * x % mod) if (t & 1) ret = ret * x % mod; return ret; }
voidNTT(ll *c, int tp){ for (int i = 0; i < lim; i++) { if (i < rev[i]) swap(c[i], c[rev[i]]); } for (int mid = 1; mid < lim; mid <<= 1) { int r = mid<<1; ll wn = fpow(~tp?G:invg, (mod-1)/r); for (int j = 0; j < lim; j += r) { ll w = 1; for (int k = 0; k < mid; k++, w = w * wn % mod) { ll x = c[j+k], y = w * c[j+k+mid] % mod; c[j+k] = (x + y) % mod; c[j+k+mid] = (x - y + mod) % mod; } } } if (tp == -1) { for (int i = 0; i < lim; i++) { c[i] = c[i] * invn % mod; } } }
inline ll calc(ll x){ return (x * x % p * O % p + x * S % p + U) % p; }
voidMul(ll *a, ll *b, ll *c){ for (int i = 0; i < lim; i++) aa[i] = a[i], bb[i] = b[i]; NTT(aa, 1); NTT(bb, 1); for (int i = 0; i < lim; i++) aa[i] = aa[i] * bb[i] % mod; NTT(aa, -1); for (int i = 0; i <= m; i++) c[i] = aa[i] % p; }
voidsolve(int n){ if (n == 1) { for (int i = 0; i <= m; i++) dp[i] = sum[i] = F[i]; return; } solve(n >> 1); tot++; Mul(dp, sum, tmp); Mul(dp, dp, dp); for (int i = 0; i <= m; i++) { sum[i] = (sum[i] + tmp[i]) % p; } if (n & 1) { Mul(dp, F, tmp); for (int i = 0; i <= m; i++) { dp[i] = tmp[i]; sum[i] = (sum[i] + tmp[i]) % p; } } }
intmain(){ scanf("%d %lld %d %lld %lld %lld", &m, &p, &N, &O, &S, &U); lim = 1; while (lim <= m + m) { lim <<= 1; l++; } invn = fpow(lim, mod-2); for (int i = 0; i < lim; i++) { rev[i] = (rev[i>>1]>>1)|((i&1)<<(l-1)); } for (int i = 1; i <= m; i++) F[i] = calc(i); solve(N); printf("%lld\n", sum[m]); return0; }