为啥我多项式数组得开 1e7 才能通过此题

#include <bits/stdc++.h>
#define Maxn 10000005
#define Nep(i, l, r) for(int i = l; i != r; ++ i)
#define Rep(i, l, r) for(int i = l; i <= r; ++ i)
#define rep(i, l, r) for(int i = l; i < r; ++ i)
#define Lep(i, l, r) for(int i = l; i >= r; -- i)
#define lep(i, l, r) for(int i = l; i > r; -- i)
#define ll long long
#define ull unsigned long long
#define int long long

int read() {
	int x = 1, res = 0, ch = getchar();
	while(ch < '0' || ch > '9') { if(ch == '-') x = -1; ch = getchar(); }
	while(ch >= '0' && ch <= '9') res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
	return x * res;
}

const int mod = 1004535809;

int qpow(int a, int b) {
    int ret = 1, bas = a;

    for (; b; b >>= 1, bas = 1LL * bas * bas % mod)
        if (b & 1)
            ret = 1LL * ret * bas % mod;

    return ret;
}

int pr[Maxn];
const int G = 3, invG = qpow(G, mod - 2);

void ntt(int f[], int q, int n) {
	rep(i, 0, n) pr[i] = (pr[i >> 1] >> 1) | ((i & 1) ? (n >> 1) : 0);
	rep(i, 0, n) if(i < pr[i]) std :: swap(f[i], f[pr[i]]); 
	for(int len = 2; len <= n; len <<= 1) {
		int d = len >> 1;
		int w = qpow(q ? G : invG, (mod - 1) / len);
		for(int k = 0; k < n; k += len) {
			int buf = 1;
			rep(i, k, k + d) {
				int temp = buf * f[i + d] % mod;
				f[i + d] = (f[i] - temp + mod) % mod; 
				f[i]     = (f[i] + temp) % mod; 
				buf = buf * w % mod;
			}
		}
	} int invn = qpow(n, mod - 2); 
	if(! q) rep(i, 0, n) (f[i] *= invn) %= mod;
}

int f[Maxn], g[Maxn], v[Maxn], q[Maxn], fac[Maxn], ifac[Maxn];

int binom(int x, int y) {
	return fac[x] * ifac[y] % mod * ifac[x - y] % mod;
}

void init() {
	fac[0] = 1; rep(i, 1, Maxn) fac[i] = fac[i - 1] * i % mod;
	ifac[Maxn - 1] = qpow(fac[Maxn - 1], mod - 2);
	Lep(i, Maxn - 2, 0) ifac[i] = ifac[i + 1] * (i + 1) % mod;
}

signed main() {
	init(); 
	int N = read(), m = read(), s = read(), lim = std :: min(m, N / s), ans = 0; 
	Rep(i, 0, lim) f[i] = binom(m, i) * fac[N] % mod * ifac[N - i * s] % mod * qpow(ifac[s], i) % mod * qpow(m - i, N - i * s) % mod * fac[i] % mod;
	Rep(i, 0, lim) g[i] = ((i % 2) ? (mod - ifac[i]) : (ifac[i])); std :: reverse(f, f + lim + 1);
	int n = 1; while(n <= lim * 2 + 2) n <<= 1;  ntt(f, 1, n), ntt(g, 1, n);
	rep(i, 0, n) f[i] = (f[i] * g[i]) % mod; ntt(f, 0, n); std :: reverse(f, f + lim + 1); 
	Rep(i, 0, lim) (ans += read() * f[i] % mod * ifac[i] % mod) %= mod;
	return printf("%lld", (ans + mod) % mod), 0;
}