#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define F(i, a, b) for (int i = (a), iee = (b); i <= iee; i++)
#define FO(i, a, b) for (int i = (a), iee = (b); i < iee; i++)
#define R(i, a, b) for (int i = (a), iee = (b); i >= iee; i--)

const int N = 1 << 18, M = 998244353;
int power(int x, int y) {
    int ans = 1;
    for (; y; y >>= 1, x = 1ll * x * x % M) if (y & 1)
        ans = 1ll * ans * x % M;
    return ans;
}

int n, m, a[N], b[N], inva[N];

struct mint {
    int val;
    static int chk(int x) { return x < 0 ? x + M : x; }
    mint(): val() {}
    mint(ll v): val(chk(v % M)) {}
    mint(int v, int w): val(v) {}
    explicit operator int() const { return val; }
    mint &operator += (mint b) { return val = chk(val + b.val - M), *this; }
    mint &operator -= (mint b) { return val = chk(val - b.val), *this; }
    mint &operator *= (mint b) { return val = 1ll * val * b.val % M, *this; }
    friend mint operator + (mint a, mint b) { return a += b; }
    friend mint operator - (mint a, mint b) { return a -= b; }
    friend mint operator * (mint a, mint b) { return a *= b; }
    friend mint operator ^ (mint x, ll y) {
        if ((y %= M - 1) < 0) y += M - 1;
        mint ans(1);
        for (; y; y >>= 1, x *= x) if (y & 1) ans *= x;
        return ans;
    }
    mint inv() const { return (*this) ^ (M - 2); }
};

void upd(int &x, ll y) { x = (x + y) % M; }
void upd(int &x, int y) { x = x + y >= M ? x + y - M : x + y; }

void force() {
    static int f[N], g[N];
    F(i, 1, m) f[i] = a[i];
    for (int _ = 2; _ <= n; _++) {
        F(i, 1, m) g[i] = f[i], f[i] = 0;
        F(i, 1, m) upd(f[min(m, b[i])], g[i]);
        R(i, m, 1) upd(f[i - 1], f[i]);
        F(i, 1, m) f[i] = 1ll * f[i] * a[i] % M;
    }
    ll ans = 0;
    F(i, 1, m) ans += f[i];
    cout << ans % M << "\n";
}

void ntt(mint *a, int n, int typ) {
    for (int i = 0, j = 0; i < n; i++) {
        if (i < j) swap(a[i], a[j]);
        for (int l = n >> 1; (j ^= l) < l; l >>= 1);
    }
    for (int m = 1, k = 2; m < n; m <<= 1, k <<= 1) {
        mint g = mint(3) ^ ((M - 1) / k * typ), o(1);
        for (int j = 0; j < n; j += k, o = 1) {
            for (int i = 0; i < m; i++, o *= g) {
                mint x = o * a[i + j + m];
                a[i + j + m] = a[i + j] - x;
                a[i + j] += x;
            }
        }
    }
    if (!~typ) {
        mint invn = mint(n).inv();
        FO(i, 0, n) a[i] *= invn;
    }
}

using poly = vector<mint>;
int sup(int n) { return 1 << (32 - __builtin_clz(n - 1)); }

poly inv(poly g) {
    int tn = g.size(), n = sup(tn);
    g.resize(n);
    poly f(n);
    f[0] = g[0].inv();
    for (int m = 1, k = 2; m < n; m <<= 1, k <<= 1) {
        poly h(&g[0], &g[k]);
        ntt(&h[0], k, 1);
        poly f0(&f[0], &f[k]);
        ntt(&f0[0], k, 1);
        FO(i, 0, k) h[i] = mint() - h[i] * f0[i];
        ntt(&h[0], k, -1);
        fill(&h[0], &h[m], mint());
        ntt(&h[0], k, 1);
        FO(i, 0, k) h[i] *= f0[i];
        ntt(&h[0], k, -1);
        copy(&h[m], &h[k], &f[m]);
    }
    f.resize(tn);
    return f;
}

struct Matrix {
    poly f[3][3];
};

Matrix solve(int l, int r) {
    if (l == r) {
        Matrix ret;
        ret.f[1][0] = ret.f[2][1] = {1};
        ret.f[0][0] = {M - inva[l]};
        int t = b[l] - l;
        mint val(1);
        F(j, l + 1, b[l]) val *= M - inva[j];
        ret.f[0][t].resize(2);
        ret.f[0][t][1] = val;
        return ret;
    }
    int mid = (l + r) >> 1;
    Matrix A = solve(l, mid), B = solve(mid + 1, r), C;
    
    int n = 0, m = 0;
    F(i, 0, 2) F(j, 0, 2) n = max<int>(n, A.f[i][j].size()), m = max<int>(m, B.f[i][j].size());
    n = sup(n + m - 1);
    F(i, 0, 2) F(j, 0, 2) {
        A.f[i][j].resize(n), B.f[i][j].resize(n), C.f[i][j].resize(n);
        ntt(&A.f[i][j][0], n, 1);
        ntt(&B.f[i][j][0], n, 1);
    }
    F(i, 0, 2) F(j, 0, 2) F(k, 0, 2) FO(t, 0, n)
        C.f[i][j][t] += A.f[i][k][t] * B.f[k][j][t];
    F(i, 0, 2) F(j, 0, 2) {
        ntt(&C.f[i][j][0], n, -1);
        while (!C.f[i][j].empty() && (int)C.f[i][j].back() == 0) C.f[i][j].pop_back();
    }
    return C;
}

void solve() {
    F(i, 1, m) inva[i] = power(a[i], M - 2);
    poly g = solve(1, m).f[0][0];
    poly f(g.begin() + 1, g.end());
    g.resize(n);
    poly h = inv(g);
    mint ans;
    FO(i, 0, min<int>(n, f.size())) ans -= f[i] * h[n - 1 - i];
    cout << (int)ans;
}

int main() {
}