#line 1 "test/compositional_inverse_of_formal_power_series_large.0.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/compositional_inverse_of_formal_power_series_large"

#line 2 "fps_composition.hpp"

#line 2 "binomial.hpp"

#include <algorithm>
#include <vector>

template <typename Tp>
class Binomial {
    std::vector<Tp> factorial_, invfactorial_;

    Binomial() : factorial_{Tp(1)}, invfactorial_{Tp(1)} {}

    void preprocess(int n) {
        if (const int nn = factorial_.size(); nn < n) {
            int k = nn;
            while (k < n) k *= 2;
            k = std::min<long long>(k, Tp::mod());
            factorial_.resize(k);
            invfactorial_.resize(k);
            for (int i = nn; i < k; ++i) factorial_[i] = factorial_[i - 1] * i;
            invfactorial_.back() = factorial_.back().inv();
            for (int i = k - 2; i >= nn; --i) invfactorial_[i] = invfactorial_[i + 1] * (i + 1);
        }
    }

public:
    static const Binomial &get(int n) {
        static Binomial bin;
        bin.preprocess(n);
        return bin;
    }

    Tp binom(int n, int m) const {
        return n < m ? Tp() : factorial_[n] * invfactorial_[m] * invfactorial_[n - m];
    }
    Tp inv(int n) const { return factorial_[n - 1] * invfactorial_[n]; }
    Tp factorial(int n) const { return factorial_[n]; }
    Tp inv_factorial(int n) const { return invfactorial_[n]; }
};
#line 2 "fft.hpp"

#line 4 "fft.hpp"
#include <cassert>
#include <iterator>
#include <memory>
#line 8 "fft.hpp"

template <typename Tp>
class FftInfo {
    static Tp least_quadratic_nonresidue() {
        for (int i = 2;; ++i)
            if (Tp(i).pow((Tp::mod() - 1) / 2) == -1) return Tp(i);
    }

    const int ordlog2_;
    const Tp zeta_;
    const Tp invzeta_;
    const Tp imag_;
    const Tp invimag_;

    mutable std::vector<Tp> root_;
    mutable std::vector<Tp> invroot_;

    FftInfo()
        : ordlog2_(__builtin_ctzll(Tp::mod() - 1)),
          zeta_(least_quadratic_nonresidue().pow((Tp::mod() - 1) >> ordlog2_)),
          invzeta_(zeta_.inv()), imag_(zeta_.pow(1LL << (ordlog2_ - 2))), invimag_(-imag_),
          root_{Tp(1), imag_}, invroot_{Tp(1), invimag_} {}

public:
    static const FftInfo &get() {
        static FftInfo info;
        return info;
    }

    Tp imag() const { return imag_; }
    Tp inv_imag() const { return invimag_; }
    Tp zeta() const { return zeta_; }
    Tp inv_zeta() const { return invzeta_; }
    const std::vector<Tp> &root(int n) const {
        // [0, n)
        assert((n & (n - 1)) == 0);
        if (const int s = root_.size(); s < n) {
            root_.resize(n);
            for (int i = __builtin_ctz(s); (1 << i) < n; ++i) {
                const int j = 1 << i;
                root_[j]    = zeta_.pow(1LL << (ordlog2_ - i - 2));
                for (int k = j + 1; k < j * 2; ++k) root_[k] = root_[k - j] * root_[j];
            }
        }
        return root_;
    }
    const std::vector<Tp> &inv_root(int n) const {
        // [0, n)
        assert((n & (n - 1)) == 0);
        if (const int s = invroot_.size(); s < n) {
            invroot_.resize(n);
            for (int i = __builtin_ctz(s); (1 << i) < n; ++i) {
                const int j = 1 << i;
                invroot_[j] = invzeta_.pow(1LL << (ordlog2_ - i - 2));
                for (int k = j + 1; k < j * 2; ++k) invroot_[k] = invroot_[k - j] * invroot_[j];
            }
        }
        return invroot_;
    }
};

inline int fft_len(int n) {
    --n;
    n |= n >> 1, n |= n >> 2, n |= n >> 4, n |= n >> 8;
    return (n | n >> 16) + 1;
}

template <typename Iterator>
inline void fft_n(Iterator a, int n) {
    using Tp = typename std::iterator_traits<Iterator>::value_type;
    assert((n & (n - 1)) == 0);
    for (int j = 0; j < n / 2; ++j) {
        auto u = a[j], v = a[j + n / 2];
        a[j] = u + v, a[j + n / 2] = u - v;
    }
    auto &&root = FftInfo<Tp>::get().root(n / 2);
    for (int i = n / 2; i >= 2; i /= 2) {
        for (int j = 0; j < i / 2; ++j) {
            auto u = a[j], v = a[j + i / 2];
            a[j] = u + v, a[j + i / 2] = u - v;
        }
        for (int j = i, m = 1; j < n; j += i, ++m)
            for (int k = j; k < j + i / 2; ++k) {
                auto u = a[k], v = a[k + i / 2] * root[m];
                a[k] = u + v, a[k + i / 2] = u - v;
            }
    }
}

template <typename Tp>
inline void fft(std::vector<Tp> &a) {
    fft_n(a.begin(), a.size());
}

template <typename Iterator>
inline void inv_fft_n(Iterator a, int n) {
    using Tp = typename std::iterator_traits<Iterator>::value_type;
    assert((n & (n - 1)) == 0);
    auto &&root = FftInfo<Tp>::get().inv_root(n / 2);
    for (int i = 2; i < n; i *= 2) {
        for (int j = 0; j < i / 2; ++j) {
            auto u = a[j], v = a[j + i / 2];
            a[j] = u + v, a[j + i / 2] = u - v;
        }
        for (int j = i, m = 1; j < n; j += i, ++m)
            for (int k = j; k < j + i / 2; ++k) {
                auto u = a[k], v = a[k + i / 2];
                a[k] = u + v, a[k + i / 2] = (u - v) * root[m];
            }
    }
    const Tp iv = Tp::mod() - Tp::mod() / n;
    for (int j = 0; j < n / 2; ++j) {
        auto u = a[j] * iv, v = a[j + n / 2] * iv;
        a[j] = u + v, a[j + n / 2] = u - v;
    }
}

template <typename Tp>
inline void inv_fft(std::vector<Tp> &a) {
    inv_fft_n(a.begin(), a.size());
}

template <typename Tp>
inline std::vector<Tp> convolution_fft(std::vector<Tp> a, std::vector<Tp> b) {
    if (a.empty() || b.empty()) return {};
    const int n   = a.size();
    const int m   = b.size();
    const int len = fft_len(n + m - 1);
    a.resize(len);
    b.resize(len);
    fft(a);
    fft(b);
    for (int i = 0; i < len; ++i) a[i] *= b[i];
    inv_fft(a);
    a.resize(n + m - 1);
    return a;
}

template <typename Tp>
inline std::vector<Tp> square_fft(std::vector<Tp> a) {
    if (a.empty()) return {};
    const int n   = a.size();
    const int len = fft_len(n * 2 - 1);
    a.resize(len);
    fft(a);
    for (int i = 0; i < len; ++i) a[i] *= a[i];
    inv_fft(a);
    a.resize(n * 2 - 1);
    return a;
}

template <typename Tp>
inline std::vector<Tp> convolution_naive(const std::vector<Tp> &a, const std::vector<Tp> &b) {
    if (a.empty() || b.empty()) return {};
    const int n = a.size();
    const int m = b.size();
    std::vector<Tp> res(n + m - 1);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) res[i + j] += a[i] * b[j];
    return res;
}

template <typename Tp>
inline std::vector<Tp> convolution(const std::vector<Tp> &a, const std::vector<Tp> &b) {
    if (std::min(a.size(), b.size()) < 60) return convolution_naive(a, b);
    if (std::addressof(a) == std::addressof(b)) return square_fft(a);
    return convolution_fft(a, b);
}
#line 2 "fps_basic.hpp"

#line 2 "semi_relaxed_conv.hpp"

#line 5 "semi_relaxed_conv.hpp"
#include <type_traits>
#include <utility>
#line 8 "semi_relaxed_conv.hpp"

// returns coefficients generated by closure
// closure: gen(index, current_product)
template <typename Tp, typename Closure>
inline std::enable_if_t<std::is_invocable_r_v<Tp, Closure, int, const std::vector<Tp> &>,
                        std::vector<Tp>>
semi_relaxed_convolution(const std::vector<Tp> &A, Closure gen, int n) {
    enum { BaseCaseSize = 32 };
    static_assert((BaseCaseSize & (BaseCaseSize - 1)) == 0);

    static const int Block[]     = {16, 16, 16, 16, 16};
    static const int BlockSize[] = {
        BaseCaseSize,
        BaseCaseSize * Block[0],
        BaseCaseSize * Block[0] * Block[1],
        BaseCaseSize * Block[0] * Block[1] * Block[2],
        BaseCaseSize * Block[0] * Block[1] * Block[2] * Block[3],
        BaseCaseSize * Block[0] * Block[1] * Block[2] * Block[3] * Block[4],
    };

    // returns (which_block, level)
    auto blockinfo = [](int ind) {
        int i = ind / BaseCaseSize, lv = 0;
        while ((i & (Block[lv] - 1)) == 0) i /= Block[lv++];
        return std::make_pair(i & (Block[lv] - 1), lv);
    };

    std::vector<Tp> B(n), AB(n);
    std::vector<std::vector<std::vector<Tp>>> dftA, dftB;

    for (int i = 0; i < n; ++i) {
        const int s = i & (BaseCaseSize - 1);

        // blocked contribution
        if (i >= BaseCaseSize && s == 0) {
            const auto [j, lv]  = blockinfo(i);
            const int blocksize = BlockSize[lv];

            if (blocksize * j == i) {
                if ((int)dftA.size() == lv) {
                    dftA.emplace_back();
                    dftB.emplace_back(Block[lv] - 1);
                }
                if ((j - 1) * blocksize < (int)A.size()) {
                    dftA[lv]
                        .emplace_back(A.begin() + (j - 1) * blocksize,
                                      A.begin() + std::min((j + 1) * blocksize, (int)A.size()))
                        .resize(blocksize * 2);
                    fft(dftA[lv][j - 1]);
                } else {
                    dftA[lv].emplace_back(blocksize * 2);
                }
            }

            dftB[lv][j - 1].resize(blocksize * 2);
            std::copy_n(B.begin() + (i - blocksize), blocksize, dftB[lv][j - 1].begin());
            std::fill_n(dftB[lv][j - 1].begin() + blocksize, blocksize, Tp());
            fft(dftB[lv][j - 1]);

            // middle product
            std::vector<Tp> mp(blocksize * 2);
            for (int k = 0; k < j; ++k)
                for (int l = 0; l < blocksize * 2; ++l)
                    mp[l] += dftA[lv][j - 1 - k][l] * dftB[lv][k][l];
            inv_fft(mp);

            for (int k = 0; k < blocksize && i + k < n; ++k) AB[i + k] += mp[k + blocksize];
        }

        // basecase contribution
        for (int j = std::max(i - s, i - (int)A.size() + 1); j < i; ++j) AB[i] += A[i - j] * B[j];
        B[i] = gen(i, AB);
        if (!A.empty()) AB[i] += A[0] * B[i];
    }

    return B;
}
#line 7 "fps_basic.hpp"

template <typename Tp>
inline int order(const std::vector<Tp> &a) {
    for (int i = 0; i < (int)a.size(); ++i)
        if (a[i] != 0) return i;
    return -1;
}

template <typename Tp>
inline std::vector<Tp> inv(const std::vector<Tp> &a, int n) {
    assert(!a.empty());
    if (n <= 0) return {};
    return semi_relaxed_convolution(
        a, [v = a[0].inv()](int n, auto &&c) { return n == 0 ? v : -c[n] * v; }, n);
}

template <typename Tp>
inline std::vector<Tp> div(const std::vector<Tp> &a, const std::vector<Tp> &b, int n) {
    assert(!b.empty());
    if (n <= 0) return {};
    return semi_relaxed_convolution(
        b,
        [&, v = b[0].inv()](int n, auto &&c) {
            if (n < (int)a.size()) return (a[n] - c[n]) * v;
            return -c[n] * v;
        },
        n);
}

template <typename Tp>
inline std::vector<Tp> deriv(const std::vector<Tp> &a) {
    const int n = (int)a.size() - 1;
    if (n <= 0) return {};
    std::vector<Tp> res(n);
    for (int i = 1; i <= n; ++i) res[i - 1] = a[i] * i;
    return res;
}

template <typename Tp>
inline std::vector<Tp> integr(const std::vector<Tp> &a, Tp c = {}) {
    const int n = a.size() + 1;
    auto &&bin  = Binomial<Tp>::get(n);
    std::vector<Tp> res(n);
    res[0] = c;
    for (int i = 1; i < n; ++i) res[i] = a[i - 1] * bin.inv(i);
    return res;
}

template <typename Tp>
inline std::vector<Tp> log(const std::vector<Tp> &a, int n) {
    return integr(div(deriv(a), a, n - 1));
}

template <typename Tp>
inline std::vector<Tp> exp(const std::vector<Tp> &a, int n) {
    if (n <= 0) return {};
    assert(!a.empty() && a[0] == 0);
    return semi_relaxed_convolution(
        deriv(a),
        [bin = Binomial<Tp>::get(n)](int n, auto &&c) {
            return n == 0 ? Tp(1) : c[n - 1] * bin.inv(n);
        },
        n);
}

template <typename Tp>
inline std::vector<Tp> pow(std::vector<Tp> a, long long e, int n) {
    if (n <= 0) return {};
    if (e == 0) {
        std::vector<Tp> res(n);
        res[0] = 1;
        return res;
    }

    const int o = order(a);
    if (o < 0 || o > n / e || (o == n / e && n % e == 0)) return std::vector<Tp>(n);
    if (o != 0) a.erase(a.begin(), a.begin() + o);

    const Tp ia0 = a[0].inv();
    const Tp a0e = a[0].pow(e);
    const Tp me  = e;

    for (int i = 0; i < (int)a.size(); ++i) a[i] *= ia0;
    a = log(a, n - o * e);
    for (int i = 0; i < (int)a.size(); ++i) a[i] *= me;
    a = exp(a, n - o * e);
    for (int i = 0; i < (int)a.size(); ++i) a[i] *= a0e;

    a.insert(a.begin(), o * e, Tp());
    return a;
}
#line 9 "fps_composition.hpp"

// returns f(g) mod x^n
// see: https://arxiv.org/abs/2404.05177
// Yasunori Kinoshita, Baitian Li. Power Series Composition in Near-Linear Time.
template <typename Tp>
inline std::vector<Tp> composition(const std::vector<Tp> &f, const std::vector<Tp> &g, int n) {
    if (n <= 0) return {};
    if (g.empty()) {
        std::vector<Tp> res(n);
        if (!f.empty()) res[0] = f[0];
        return res;
    }

    // [y^(-1)] (f(y) / (-g(x) + y)) mod x^n
    // R[x]((y^(-1)))
    auto rec = [g0 = g[0]](auto &&rec, const std::vector<Tp> &P, const std::vector<Tp> &Q, int d,
                           int n) {
        if (n == 1) {
            std::vector<Tp> invQ(d + 1);
            auto &&bin = Binomial<Tp>::get(d * 2);
            Tp gg      = 1;
            for (int i = 0; i <= d; ++i) invQ[d - i] = bin.binom(d + i - 1, d - 1) * gg, gg *= g0;
            // invQ[i] = [y^(-2d + i)]Q
            // P[0,d-1] * invQ[-2d,-d] => [0,d-1] * [0,d]
            // take [-d,-1] => take [d,2d-1]
            auto PinvQ = convolution(P, invQ);
            PinvQ.erase(PinvQ.begin(), PinvQ.begin() + d);
            PinvQ.resize(d);
            return PinvQ;
        }

        std::vector<Tp> dftQ(d * n * 4);
        for (int i = 0; i < d; ++i)
            for (int j = 0; j < n; ++j) dftQ[i * (n * 2) + j] = Q[i * n + j];
        dftQ[d * n * 2] = 1;
        fft(dftQ);
        std::vector<Tp> V(d * n * 2);
        for (int i = 0; i < d * n * 4; i += 2) V[i / 2] = dftQ[i] * dftQ[i + 1];
        inv_fft(V);
        V[0] -= 1;

        for (int i = 1; i < d * 2; ++i)
            for (int j = 0; j < n / 2; ++j) V[i * (n / 2) + j] = V[i * n + j];
        V.resize(d * n);

        const auto T = rec(rec, P, V, d * 2, n / 2);

        std::vector<Tp> dftT(d * n * 2);
        for (int i = 0; i < d * 2; ++i)
            for (int j = 0; j < n / 2; ++j) dftT[i * n + j] = T[i * (n / 2) + j];
        fft(dftT);

        std::vector<Tp> U(d * n * 4);
        for (int i = 0; i < d * n * 4; i += 2) {
            U[i]     = dftT[i / 2] * dftQ[i + 1];
            U[i + 1] = dftT[i / 2] * dftQ[i];
        }
        inv_fft(U);

        // [-2d,d-1] => [0,3d-1]
        // take [-d,-1] => take [d,2d-1]
        for (int i = 0; i < d; ++i)
            for (int j = 0; j < n; ++j) U[i * n + j] = U[(i + d) * (n * 2) + j];
        U.resize(d * n);
        return U;
    };

    int k = 1;
    while (k < std::max(n, (int)f.size())) k *= 2;
    std::vector<Tp> Q(k);
    for (int i = 0; i < std::min(k, (int)g.size()); ++i) Q[i] = -g[i];

    auto res = rec(rec, f, Q, 1, k);
    res.resize(n);
    return res;
}

// returns [x^k]gf^0, [x^k]gf, ..., [x^k]gf^(n-1)
// see: https://noshi91.hatenablog.com/entry/2024/03/16/224034
// noshi91. FPS の合成と逆関数、冪乗の係数列挙 Θ(n (log(n))^2)
template <typename Tp>
inline std::vector<Tp> enum_kth_term_of_power(const std::vector<Tp> &f, const std::vector<Tp> &g,
                                              int k, int n) {
    if (k < 0 || n <= 0) return {};
    if (f.empty()) {
        std::vector<Tp> res(n);
        if (k < (int)g.size()) res[0] = g[k];
        return res;
    }

    // [x^k] (g(x) / (-f(x) + y))
    // R[x]((y^(-1)))
    std::vector<Tp> P(g), Q(k + 1);
    P.resize(k + 1);
    for (int i = 0; i < std::min(k + 1, (int)f.size()); ++i) Q[i] = -f[i];

    int d = 1;
    for (; k; d *= 2, k /= 2) {
        const int len = fft_len((d * 2) * ((k + 1) * 2) - 1);
        std::vector<Tp> dftP(len), dftQ(len);
        for (int i = 0; i < d; ++i)
            for (int j = 0; j <= k; ++j) {
                dftP[i * ((k + 1) * 2) + j] = P[i * (k + 1) + j];
                dftQ[i * ((k + 1) * 2) + j] = Q[i * (k + 1) + j];
            }
        dftQ[d * (k + 1) * 2] = 1;
        fft(dftP);
        fft(dftQ);

        P.resize(len / 2);
        Q.resize(len / 2);
        if (k & 1) {
            auto &&root = FftInfo<Tp>::get().inv_root(len / 2);
            for (int i = 0; i < len; i += 2) {
                P[i / 2] = (dftP[i] * dftQ[i + 1] - dftP[i + 1] * dftQ[i]).div_by_2() * root[i / 2];
                Q[i / 2] = dftQ[i] * dftQ[i + 1];
            }
        } else {
            for (int i = 0; i < len; i += 2) {
                P[i / 2] = (dftP[i] * dftQ[i + 1] + dftP[i + 1] * dftQ[i]).div_by_2();
                Q[i / 2] = dftQ[i] * dftQ[i + 1];
            }
        }
        inv_fft(P);
        inv_fft(Q);
        if (d * (k + 1) * 4 >= len) Q[(d * (k + 1) * 4) % len] -= 1;

        for (int i = 1; i < d * 2; ++i)
            for (int j = 0; j <= k / 2; ++j) {
                P[i * (k / 2 + 1) + j] = P[i * (k + 1) + j];
                Q[i * (k / 2 + 1) + j] = Q[i * (k + 1) + j];
            }
        P.resize(d * 2 * (k / 2 + 1));
        Q.resize(d * 2 * (k / 2 + 1));
    }

    std::vector<Tp> invQ(n + 1);
    auto &&bin = Binomial<Tp>::get(d + n);
    Tp ff      = 1;
    for (int i = 0; i <= n; ++i) invQ[n - i] = bin.binom(d + i - 1, d - 1) * ff, ff *= f[0];
    // invQ[i] = [y^(-2d + i)]Q
    // P[0,d-1] * invQ[-(d+n),-d] => [0,d-1] * [0,n]
    auto PinvQ = convolution(P, invQ);
    // take [-n,-1] => take [d,d+n-1]
    PinvQ.erase(PinvQ.begin(), PinvQ.begin() + d);
    PinvQ.resize(n);
    // output => [-1,-n] reverse
    // before I just reverse it and mistaken something.
    std::reverse(PinvQ.begin(), PinvQ.end());
    return PinvQ;
}

// returns g s.t. f(g) = g(f) = x mod x^n
template <typename Tp>
inline std::vector<Tp> reversion(std::vector<Tp> f, int n) {
    if (n <= 0 || f.size() < 2) return {};
    assert(f[1] != 0);
    const auto if1 = f[1].inv();
    if (n == 1) return {Tp()};
    f.resize(n);
    Tp ff = 1;
    for (int i = 1; i < n; ++i) f[i] *= ff *= if1;
    auto a     = enum_kth_term_of_power(f, {Tp(1)}, n - 1, n);
    auto &&bin = Binomial<Tp>::get(n);
    for (int i = 1; i < n; ++i) a[i] *= (n - 1) * bin.inv(i);
    auto b = pow(std::vector(a.rbegin(), a.rend() - 1), Tp(1 - n).inv().val(), n - 1);
    for (int i = 0; i < n - 1; ++i) b[i] *= if1;
    b.insert(b.begin(), Tp());
    return b;
}
#line 2 "modint.hpp"

#include <iostream>
#line 5 "modint.hpp"

template <unsigned Mod>
class ModInt {
    static_assert((Mod >> 31) == 0, "`Mod` must less than 2^(31)");
    template <typename Int>
    static std::enable_if_t<std::is_integral_v<Int>, unsigned> safe_mod(Int v) {
        using D = std::common_type_t<Int, unsigned>;
        return (v %= (int)Mod) < 0 ? (D)(v + (int)Mod) : (D)v;
    }

    struct PrivateConstructor {};
    static inline PrivateConstructor private_constructor{};
    ModInt(PrivateConstructor, unsigned v) : v_(v) {}

    unsigned v_;

public:
    static unsigned mod() { return Mod; }
    static ModInt from_raw(unsigned v) { return ModInt(private_constructor, v); }
    ModInt() : v_() {}
    template <typename Int, typename std::enable_if_t<std::is_signed_v<Int>, int> = 0>
    ModInt(Int v) : v_(safe_mod(v)) {}
    template <typename Int, typename std::enable_if_t<std::is_unsigned_v<Int>, int> = 0>
    ModInt(Int v) : v_(v % Mod) {}
    unsigned val() const { return v_; }

    ModInt operator-() const { return from_raw(v_ == 0 ? v_ : Mod - v_); }
    ModInt pow(long long e) const {
        if (e < 0) return inv().pow(-e);
        for (ModInt x(*this), res(from_raw(1));; x *= x) {
            if (e & 1) res *= x;
            if ((e >>= 1) == 0) return res;
        }
    }
    ModInt inv() const {
        int x1 = 1, x3 = 0, a = val(), b = Mod;
        while (b) {
            int q = a / b, x1_old = x1, a_old = a;
            x1 = x3, x3 = x1_old - x3 * q, a = b, b = a_old - b * q;
        }
        return from_raw(x1 < 0 ? x1 + (int)Mod : x1);
    }
    template <bool Odd = (Mod & 1)>
    std::enable_if_t<Odd, ModInt> div_by_2() const {
        if (v_ & 1) return from_raw((v_ + Mod) >> 1);
        return from_raw(v_ >> 1);
    }

    ModInt &operator+=(const ModInt &a) {
        if ((v_ += a.v_) >= Mod) v_ -= Mod;
        return *this;
    }
    ModInt &operator-=(const ModInt &a) {
        if ((v_ += Mod - a.v_) >= Mod) v_ -= Mod;
        return *this;
    }
    ModInt &operator*=(const ModInt &a) {
        v_ = (unsigned long long)v_ * a.v_ % Mod;
        return *this;
    }
    ModInt &operator/=(const ModInt &a) { return *this *= a.inv(); }

    friend ModInt operator+(const ModInt &a, const ModInt &b) { return ModInt(a) += b; }
    friend ModInt operator-(const ModInt &a, const ModInt &b) { return ModInt(a) -= b; }
    friend ModInt operator*(const ModInt &a, const ModInt &b) { return ModInt(a) *= b; }
    friend ModInt operator/(const ModInt &a, const ModInt &b) { return ModInt(a) /= b; }
    friend bool operator==(const ModInt &a, const ModInt &b) { return a.v_ == b.v_; }
    friend bool operator!=(const ModInt &a, const ModInt &b) { return a.v_ != b.v_; }
    friend std::istream &operator>>(std::istream &a, ModInt &b) {
        int v;
        a >> v;
        b.v_ = safe_mod(v);
        return a;
    }
    friend std::ostream &operator<<(std::ostream &a, const ModInt &b) { return a << b.val(); }
};
#line 7 "test/compositional_inverse_of_formal_power_series_large.0.test.cpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    using mint = ModInt<998244353>;
    int n;
    std::cin >> n;
    std::vector<mint> f(n);
    for (int i = 0; i < n; ++i) std::cin >> f[i];
    const auto g = reversion(f, n);
    for (int i = 0; i < n; ++i) std::cout << g[i] << ' ';
    return 0;
}
/*#line 1 "test/compositional_inverse_of_formal_power_series_large.0.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/compositional_inverse_of_formal_power_series_large"

#line 2 "fps_composition.hpp"

#line 2 "binomial.hpp"

#include <algorithm>
#include <vector>

template <typename Tp>
class Binomial {
    std::vector<Tp> factorial_, invfactorial_;

    Binomial() : factorial_{Tp(1)}, invfactorial_{Tp(1)} {}

    void preprocess(int n) {
        if (const int nn = factorial_.size(); nn < n) {
            int k = nn;
            while (k < n) k *= 2;
            k = std::min<long long>(k, Tp::mod());
            factorial_.resize(k);
            invfactorial_.resize(k);
            for (int i = nn; i < k; ++i) factorial_[i] = factorial_[i - 1] * i;
            invfactorial_.back() = factorial_.back().inv();
            for (int i = k - 2; i >= nn; --i) invfactorial_[i] = invfactorial_[i + 1] * (i + 1);
        }
    }

public:
    static const Binomial &get(int n) {
        static Binomial bin;
        bin.preprocess(n);
        return bin;
    }

    Tp binom(int n, int m) const {
        return n < m ? Tp() : factorial_[n] * invfactorial_[m] * invfactorial_[n - m];
    }
    Tp inv(int n) const { return factorial_[n - 1] * invfactorial_[n]; }
    Tp factorial(int n) const { return factorial_[n]; }
    Tp inv_factorial(int n) const { return invfactorial_[n]; }
};
#line 2 "fft.hpp"

#line 4 "fft.hpp"
#include <cassert>
#include <iterator>
#include <memory>
#line 8 "fft.hpp"

template <typename Tp>
class FftInfo {
    static Tp least_quadratic_nonresidue() {
        for (int i = 2;; ++i)
            if (Tp(i).pow((Tp::mod() - 1) / 2) == -1) return Tp(i);
    }

    const int ordlog2_;
    const Tp zeta_;
    const Tp invzeta_;
    const Tp imag_;
    const Tp invimag_;

    mutable std::vector<Tp> root_;
    mutable std::vector<Tp> invroot_;

    FftInfo()
        : ordlog2_(__builtin_ctzll(Tp::mod() - 1)),
          zeta_(least_quadratic_nonresidue().pow((Tp::mod() - 1) >> ordlog2_)),
          invzeta_(zeta_.inv()), imag_(zeta_.pow(1LL << (ordlog2_ - 2))), invimag_(-imag_),
          root_{Tp(1), imag_}, invroot_{Tp(1), invimag_} {}

public:
    static const FftInfo &get() {
        static FftInfo info;
        return info;
    }

    Tp imag() const { return imag_; }
    Tp inv_imag() const { return invimag_; }
    Tp zeta() const { return zeta_; }
    Tp inv_zeta() const { return invzeta_; }
    const std::vector<Tp> &root(int n) const {
        // [0, n)
        assert((n & (n - 1)) == 0);
        if (const int s = root_.size(); s < n) {
            root_.resize(n);
            for (int i = __builtin_ctz(s); (1 << i) < n; ++i) {
                const int j = 1 << i;
                root_[j]    = zeta_.pow(1LL << (ordlog2_ - i - 2));
                for (int k = j + 1; k < j * 2; ++k) root_[k] = root_[k - j] * root_[j];
            }
        }
        return root_;
    }
    const std::vector<Tp> &inv_root(int n) const {
        // [0, n)
        assert((n & (n - 1)) == 0);
        if (const int s = invroot_.size(); s < n) {
            invroot_.resize(n);
            for (int i = __builtin_ctz(s); (1 << i) < n; ++i) {
                const int j = 1 << i;
                invroot_[j] = invzeta_.pow(1LL << (ordlog2_ - i - 2));
                for (int k = j + 1; k < j * 2; ++k) invroot_[k] = invroot_[k - j] * invroot_[j];
            }
        }
        return invroot_;
    }
};

inline int fft_len(int n) {
    --n;
    n |= n >> 1, n |= n >> 2, n |= n >> 4, n |= n >> 8;
    return (n | n >> 16) + 1;
}

template <typename Iterator>
inline void fft_n(Iterator a, int n) {
    using Tp = typename std::iterator_traits<Iterator>::value_type;
    assert((n & (n - 1)) == 0);
    for (int j = 0; j < n / 2; ++j) {
        auto u = a[j], v = a[j + n / 2];
        a[j] = u + v, a[j + n / 2] = u - v;
    }
    auto &&root = FftInfo<Tp>::get().root(n / 2);
    for (int i = n / 2; i >= 2; i /= 2) {
        for (int j = 0; j < i / 2; ++j) {
            auto u = a[j], v = a[j + i / 2];
            a[j] = u + v, a[j + i / 2] = u - v;
        }
        for (int j = i, m = 1; j < n; j += i, ++m)
            for (int k = j; k < j + i / 2; ++k) {
                auto u = a[k], v = a[k + i / 2] * root[m];
                a[k] = u + v, a[k + i / 2] = u - v;
            }
    }
}

template <typename Tp>
inline void fft(std::vector<Tp> &a) {
    fft_n(a.begin(), a.size());
}

template <typename Iterator>
inline void inv_fft_n(Iterator a, int n) {
    using Tp = typename std::iterator_traits<Iterator>::value_type;
    assert((n & (n - 1)) == 0);
    auto &&root = FftInfo<Tp>::get().inv_root(n / 2);
    for (int i = 2; i < n; i *= 2) {
        for (int j = 0; j < i / 2; ++j) {
            auto u = a[j], v = a[j + i / 2];
            a[j] = u + v, a[j + i / 2] = u - v;
        }
        for (int j = i, m = 1; j < n; j += i, ++m)
            for (int k = j; k < j + i / 2; ++k) {
                auto u = a[k], v = a[k + i / 2];
                a[k] = u + v, a[k + i / 2] = (u - v) * root[m];
            }
    }
    const Tp iv = Tp::mod() - Tp::mod() / n;
    for (int j = 0; j < n / 2; ++j) {
        auto u = a[j] * iv, v = a[j + n / 2] * iv;
        a[j] = u + v, a[j + n / 2] = u - v;
    }
}

template <typename Tp>
inline void inv_fft(std::vector<Tp> &a) {
    inv_fft_n(a.begin(), a.size());
}

template <typename Tp>
inline std::vector<Tp> convolution_fft(std::vector<Tp> a, std::vector<Tp> b) {
    if (a.empty() || b.empty()) return {};
    const int n   = a.size();
    const int m   = b.size();
    const int len = fft_len(n + m - 1);
    a.resize(len);
    b.resize(len);
    fft(a);
    fft(b);
    for (int i = 0; i < len; ++i) a[i] *= b[i];
    inv_fft(a);
    a.resize(n + m - 1);
    return a;
}

template <typename Tp>
inline std::vector<Tp> square_fft(std::vector<Tp> a) {
    if (a.empty()) return {};
    const int n   = a.size();
    const int len = fft_len(n * 2 - 1);
    a.resize(len);
    fft(a);
    for (int i = 0; i < len; ++i) a[i] *= a[i];
    inv_fft(a);
    a.resize(n * 2 - 1);
    return a;
}

template <typename Tp>
inline std::vector<Tp> convolution_naive(const std::vector<Tp> &a, const std::vector<Tp> &b) {
    if (a.empty() || b.empty()) return {};
    const int n = a.size();
    const int m = b.size();
    std::vector<Tp> res(n + m - 1);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) res[i + j] += a[i] * b[j];
    return res;
}

template <typename Tp>
inline std::vector<Tp> convolution(const std::vector<Tp> &a, const std::vector<Tp> &b) {
    if (std::min(a.size(), b.size()) < 60) return convolution_naive(a, b);
    if (std::addressof(a) == std::addressof(b)) return square_fft(a);
    return convolution_fft(a, b);
}
#line 2 "fps_basic.hpp"

#line 2 "semi_relaxed_conv.hpp"

#line 5 "semi_relaxed_conv.hpp"
#include <type_traits>
#include <utility>
#line 8 "semi_relaxed_conv.hpp"

// returns coefficients generated by closure
// closure: gen(index, current_product)
template <typename Tp, typename Closure>
inline std::enable_if_t<std::is_invocable_r_v<Tp, Closure, int, const std::vector<Tp> &>,
                        std::vector<Tp>>
semi_relaxed_convolution(const std::vector<Tp> &A, Closure gen, int n) {
    enum { BaseCaseSize = 32 };
    static_assert((BaseCaseSize & (BaseCaseSize - 1)) == 0);

    static const int Block[]     = {16, 16, 16, 16, 16};
    static const int BlockSize[] = {
        BaseCaseSize,
        BaseCaseSize * Block[0],
        BaseCaseSize * Block[0] * Block[1],
        BaseCaseSize * Block[0] * Block[1] * Block[2],
        BaseCaseSize * Block[0] * Block[1] * Block[2] * Block[3],
        BaseCaseSize * Block[0] * Block[1] * Block[2] * Block[3] * Block[4],
    };

    // returns (which_block, level)
    auto blockinfo = [](int ind) {
        int i = ind / BaseCaseSize, lv = 0;
        while ((i & (Block[lv] - 1)) == 0) i /= Block[lv++];
        return std::make_pair(i & (Block[lv] - 1), lv);
    };

    std::vector<Tp> B(n), AB(n);
    std::vector<std::vector<std::vector<Tp>>> dftA, dftB;

    for (int i = 0; i < n; ++i) {
        const int s = i & (BaseCaseSize - 1);

        // blocked contribution
        if (i >= BaseCaseSize && s == 0) {
            const auto [j, lv]  = blockinfo(i);
            const int blocksize = BlockSize[lv];

            if (blocksize * j == i) {
                if ((int)dftA.size() == lv) {
                    dftA.emplace_back();
                    dftB.emplace_back(Block[lv] - 1);
                }
                if ((j - 1) * blocksize < (int)A.size()) {
                    dftA[lv]
                        .emplace_back(A.begin() + (j - 1) * blocksize,
                                      A.begin() + std::min((j + 1) * blocksize, (int)A.size()))
                        .resize(blocksize * 2);
                    fft(dftA[lv][j - 1]);
                } else {
                    dftA[lv].emplace_back(blocksize * 2);
                }
            }

            dftB[lv][j - 1].resize(blocksize * 2);
            std::copy_n(B.begin() + (i - blocksize), blocksize, dftB[lv][j - 1].begin());
            std::fill_n(dftB[lv][j - 1].begin() + blocksize, blocksize, Tp());
            fft(dftB[lv][j - 1]);

            // middle product
            std::vector<Tp> mp(blocksize * 2);
            for (int k = 0; k < j; ++k)
                for (int l = 0; l < blocksize * 2; ++l)
                    mp[l] += dftA[lv][j - 1 - k][l] * dftB[lv][k][l];
            inv_fft(mp);

            for (int k = 0; k < blocksize && i + k < n; ++k) AB[i + k] += mp[k + blocksize];
        }

        // basecase contribution
        for (int j = std::max(i - s, i - (int)A.size() + 1); j < i; ++j) AB[i] += A[i - j] * B[j];
        B[i] = gen(i, AB);
        if (!A.empty()) AB[i] += A[0] * B[i];
    }

    return B;
}
#line 7 "fps_basic.hpp"

template <typename Tp>
inline int order(const std::vector<Tp> &a) {
    for (int i = 0; i < (int)a.size(); ++i)
        if (a[i] != 0) return i;
    return -1;
}

template <typename Tp>
inline std::vector<Tp> inv(const std::vector<Tp> &a, int n) {
    assert(!a.empty());
    if (n <= 0) return {};
    return semi_relaxed_convolution(
        a, [v = a[0].inv()](int n, auto &&c) { return n == 0 ? v : -c[n] *
}*/