const int MOD = 998244353;

int add(int a, int b) {
    return a >= MOD - b ? a - MOD + b : a + b;
}

int sub(int a, int b) {
    return a >= b ? a - b : a - b + MOD;
}

int mul(int a, int b) {
    return (1ll * a * b) % MOD;
}

int pw(int x, int n) {
    int res = 1;
    while (n) {
        if (n % 2 == 0) {
            x = mul(x, x);
            n /= 2;
        } else {
            res = mul(res, x);
            --n;
        }
    }
    return res;
}

const int G = 3;

void fft(vector<int>& a, bool inv = false) {
    int n = a.size();
    int k = 0;
    while ((1 << k) < n) ++k;
    static vector<int> rev = {0}, power = {0, 1};
    rev.resize(n);
    for (int i = 1; i < n; ++i) {
        rev[i] = rev[i / 2] / 2 + ((i & 1) << (k - 1));
        if (i < rev[i]) swap(a[i], a[rev[i]]);
    }
    for (int l = 1; l < n; l *= 2) {
        if (l == (int)power.size()) {
            power.resize(2 * l);
            int w = pw(G, (MOD - 1) / 2 / l);
            for (int i = l; i < 2 * l; ++i) {
                power[i] = power[i / 2];
                if (i & 1) {
                    power[i] = mul(power[i], w);
                }
            }
        }
        for (int i = 0; i < n; i += 2 * l) {
            for (int j = 0; j < l; ++j) {
                int x = a[i + j], y = mul(a[i + j + l], power[j + l]);
                a[i + j] = add(x, y);
                a[i + j + l] = sub(x, y);
            }
        }
    }
    if (inv) {
        reverse(a.begin() + 1, a.end());
        int anti = pw(n, MOD - 2);
        for (int i = 0; i < n; ++i) {
            a[i] = mul(a[i], anti);
        }
    }
}

vector<int> operator*(vector<int> a, vector<int> b) {
    int sz = a.size() + b.size() - 1;
    int k = 0;
    while ((1 << k) < sz) ++k;
    a.resize(1 << k); b.resize(1 << k);
    fft(a); fft(b);
    for (int i = 0; i < (1 << k); ++i) {
        a[i] = mul(a[i], b[i]);
    }
    fft(a, true);
    a.resize(sz);
    return a;
}