快速傅里叶变换（FFT）快速数论变换（NTT）

const int MAXN = 5000005;
const ll MOD = 998244353;
const ll G = 3;

inline ll qpow(ll a, ll k) {
    ll ret = 1;
    while (k) {
        if (k & 1) ret = ret * a % MOD;
        a = a * a % MOD;
        k >>= 1;
    }
    return ret;
}
inline ll inv(ll a) {
    return qpow(a, MOD - 2);
}

namespace FFT {
    int n, r[MAXN];
    void NTT(ll *a, int op) {
        int k = 0;
        for (; (1 << k) < n; ++k);
        for (int i = 0; i < n; ++i) {
            r[i] = r[i >> 1] >> 1 | (i & 1) << (k - 1);
            if (i < r[i]) swap(a[i], a[r[i]]);
        }
        for (int l = 2; l <= n; l <<= 1) {
            int m = l >> 1;
            ll w = qpow(G, (MOD - 1) / l);
            if (op == -1) w = inv(w);
            for (int i = 0; i < n; i += l) {
                ll wk = 1;
                for (int j = 0; j < m; ++j, wk = wk * w % MOD) {
                    ll p = a[i + j], q = wk * a[i + j + m] % MOD;
                    a[i + j] = (p + q) % MOD;
                    a[i + j + m] = (p - q + MOD) % MOD;
                }
            }
        }
    }
    void DFT(ll *a) {
        NTT(a, 1);
    }
    void IDFT(ll *a) {
        NTT(a, -1);
        ll inv = qpow(n, MOD - 2);
        for (int i = 0; i < n; ++i)
            a[i] = a[i] * inv % MOD;
    }
};