#pragma once

#include <vector>
#include <assert.h>
#include <algorithm>
#include <string>
#include <iostream>
#include <utility>
#include <iterator>
#include <array>
#include <stdio.h>
#include <ctype.h>
#include <stdint.h>

using u32 = unsigned;
using u64 = unsigned long long;
#define int u32

namespace nachia {
template <unsigned MOD> struct PrimitiveRoot {
    static constexpr u64 powm(u64 a, u64 i) {
        u64 res = 1, aa = a;

        while (i) {
            if (i & 1)
                res = res * aa % MOD;

            aa = aa * aa % MOD, i >>= 1;
        }

        return res;
    }

    static constexpr bool ExamineVal(unsigned g) {
        u32 t = MOD - 1;

        for (u64 d = 2; d * d <= t; ++d)
            if (t % d == 0) {
                if (powm(g, (MOD - 1) / d) == 1)
                    return 0;

                while (t % d == 0)
                    t /= d;
            }

        if (t ^ 1)
            if (powm(g, (MOD - 1) / t) == 1)
                return false;

        return true;
    }

    static constexpr unsigned GetVal() {
        for (unsigned x = 2; x < MOD; x++)
            if (ExamineVal(x))
                return x;

        return 0;
    }

    static const unsigned val = GetVal();
};

template <class Modint> class Comb {
private:
    std::vector <Modint> F;
    std::vector <Modint> iF;
public:
    void extend(int newN) {
        int prevN = (int)F.size() - 1;
        if (prevN >= newN)
            return;

        F.resize(newN + 1), iF.resize(newN + 1);

        for (u32 i = prevN + 1; i <= newN; i++)
            F[i] = F[i - 1] * Modint::raw(i);

        iF[newN] = F[newN].inv();

        for (int i = newN; i > prevN; i--)
            iF[i - 1] = iF[i] * Modint::raw(i);
    }

    Comb(int n = 1) {
        F.assign(2, Modint(1));
        iF.assign(2, Modint(1));
        extend(n);
    }

    constexpr inline Modint factorial(int n) const {
        return F[n];
    }

    constexpr inline Modint invFactorial(int n) const {
        return iF[n];
    }

    constexpr inline Modint invOf(int n) const {
        return iF[n] * F[n - 1];
    }

    constexpr inline Modint comb(int n, int r) const {
        if (n < 0 || n < r || r < 0)
            return Modint(0);

        return F[n] * iF[r] * iF[n - r];
    }

    constexpr inline Modint invComb(int n, int r) const {
        if (n < 0 || n < r || r < 0)
            return Modint(0);

        return iF[n] * F[r] * F[n - r];
    }

    constexpr inline Modint perm(int n, int r) const {
        if (n < 0 || n < r || r < 0)
            return Modint(0);

        return F[n] * iF[n - r];
    }

    constexpr inline Modint invPerm(int n, int r) const {
        if (n < 0 || n < r || r < 0)
            return Modint(0);

        return iF[n] * F[n - r];
    }

    constexpr inline Modint operator()(int n, int r) const {
        return comb(n, r);
    }
};

}
namespace nachia {

inline int MsbIndex(unsigned long long x) noexcept {
#ifdef __GNUC__
    return 63 - __builtin_clzll(x);
#else
    using u64 = unsigned long long;
    int q = (x >> 32) ? 32 : 0;
    auto m = x >> q;
    constexpr u64 hi = 0x8888'8888;
    constexpr u64 mi = 0x1111'1111;
    m = (((m | ~(hi - (m & ~hi))) & hi) * mi) >> 35;
    m = (((m | ~(hi - (x & ~hi))) & hi) * mi) >> 31;
    q += (m & 0xf) << 2;
    q += 0x3333'3333'2222'1100 >> (((x >> q) & 0xf) << 2) & 0xf;
    return q;
#endif
}

inline int LsbIndex(unsigned long long x) noexcept {
#ifdef __GNUC__
    return __builtin_ctzll(x);
#else
    return MsbIndex(x & -x);
#endif
}

template <class mint> struct NttInterface {
    template <class Iter> void Butterfly(Iter, int) const {}
    template <class Iter> void IButterfly(Iter, int) const {}
};

template <class mint> struct NttFromAcl : NttInterface<mint> {
    static u32 ceil_pow2(int n) {
        u32 x = 0;

        while ((1U << x) < (u32)(n))
            ++x;

        return x;
    }

    static constexpr u32 bsf_constexpr(unsigned n) {
        u32 x = 0;

        while (!(n & (1 << x)))
            ++x;

        return x;
    }

    struct fft_info {
        static constexpr u32 g = nachia::PrimitiveRoot<mint::mod()>::val;
        static constexpr int rank2 = bsf_constexpr(mint::mod() - 1);
        std::array < mint, rank2 + 1 > root;
        std::array < mint, rank2 + 1 > iroot;

        std::array < mint, std::max(0u, rank2 - 1) > rate2;
        std::array < mint, std::max(0u, rank2 - 1) > irate2;

        std::array < mint, std::max(0u, rank2 - 2) > rate3;
        std::array < mint, std::max(0u, rank2 - 2) > irate3;

        constexpr inline fft_info() {
            root[rank2] = mint(g).pow((mint::mod() - 1) >> rank2), iroot[rank2] = root[rank2].inv();
            for (u32 i = rank2 - 1; i >= 0; i--) root[i] = root[i + 1] * root[i + 1], iroot[i] = iroot[i + 1] * iroot[i + 1];
            mint prod = 1, iprod = 1;
            for (u32 i = 0; i <= rank2 - 2; i++)
                rate2[i] = root[i + 2] * prod, irate2[i] = iroot[i + 2] * iprod, prod *= iroot[i + 2], iprod *= root[i + 2];

            prod = iprod = 1;

            for (u32 i = 0; i ^ rank2 - 2; i++)
                rate3[i] = root[i + 3] * prod, irate3[i] = iroot[i + 3] * iprod, prod *= iroot[i + 3], iprod *= root[i + 3];
        }
    };

    template<class RandomAccessIterator>
    void Butterfly(RandomAccessIterator a, int n) const {
        int h = ceil_pow2(n);

        static const fft_info info;

        int len = 0;

        while (len < h) {
            if (h - len == 1) {
                int p = 1 << (h - len - 1);
                mint rot = 1;

                for (int s = 0; s < (1 << len); s++) {
                    int offset = s << (h - len);

                    for (int i = 0; i < p; i++) {
                        auto l = a[i + offset];
                        auto r = a[i + offset + p] * rot;
                        a[i + offset] = l + r;
                        a[i + offset + p] = l - r;
                    }

                    if (s + 1 != (1 << len))
                        rot *= info.rate2[LsbIndex(~(u32)(s))];
                }

                len++;
            } else {
                int p = 1 << (h - len - 2);
                mint rot = 1, imag = info.root[2];

                for (int s = 0; s < (1 << len); s++) {
                    mint rot2 = rot * rot;
                    mint rot3 = rot2 * rot;
                    int offset = s << (h - len);

                    for (int i = 0; i < p; i++) {
                        auto mod2 = 1ULL * mint::mod() * mint::mod();
                        auto a0 = 1ULL * a[i + offset].val();
                        auto a1 = 1ULL * a[i + offset + p].val() * rot.val();
                        auto a2 = 1ULL * a[i + offset + 2 * p].val() * rot2.val();
                        auto a3 = 1ULL * a[i + offset + 3 * p].val() * rot3.val();
                        auto a1na3imag = 1ULL * mint(a1 + mod2 - a3).val() * imag.val();
                        auto na2 = mod2 - a2;
                        a[i + offset] = a0 + a2 + a1 + a3;
                        a[i + offset + 1 * p] = a0 + a2 + (2 * mod2 - (a1 + a3));
                        a[i + offset + 2 * p] = a0 + na2 + a1na3imag;
                        a[i + offset + 3 * p] = a0 + na2 + (mod2 - a1na3imag);
                    }

                    if (s + 1 != (1 << len))
                        rot *= info.rate3[LsbIndex(~(u32)(s))];
                }

                len += 2;
            }
        }
    }

    template<class RandomAccessIterator>
    void IButterfly(RandomAccessIterator a, int n) const {
        int h = ceil_pow2(n);

        static const fft_info info;
        constexpr int MOD = mint::mod();

        int len = h;

        while (len) {
            if (len == 1) {
                int p = 1 << (h - len);
                mint irot = 1;

                for (int s = 0; s < (1 << (len - 1)); s++) {
                    int offset = s << (h - len + 1);

                    for (int i = 0; i < p; i++) {
                        auto l = a[i + offset];
                        auto r = a[i + offset + p];
                        a[i + offset] = l + r;
                        a[i + offset + p] = (u64)(MOD + l.val() - r.val()) * irot.val();
                    }

                    if (s + 1 != (1 << (len - 1)))
                        irot *= info.irate2[LsbIndex(~(u32)(s))];
                }

                len--;
            } else {
                int p = 1 << (h - len);
                mint irot = 1, iimag = info.iroot[2];

                for (int s = 0; s < (1 << (len - 2)); s++) {
                    mint irot2 = irot * irot;
                    mint irot3 = irot2 * irot;
                    int offset = s << (h - len + 2);

                    for (int i = 0; i < p; i++) {
                        auto a0 = 1ULL * a[i + offset + 0 * p].val();
                        auto a1 = 1ULL * a[i + offset + 1 * p].val();
                        auto a2 = 1ULL * a[i + offset + 2 * p].val();
                        auto a3 = 1ULL * a[i + offset + 3 * p].val();

                        auto a2na3iimag = 1ULL * mint((MOD + a2 - a3) * iimag.val()).val();

                        a[i + offset] = a0 + a1 + a2 + a3;
                        a[i + offset + 1 * p] = (a0 + (MOD - a1) + a2na3iimag) * irot.val();
                        a[i + offset + 2 * p] = (a0 + a1 + (MOD - a2) + (MOD - a3)) * irot2.val();
                        a[i + offset + 3 * p] = (a0 + (MOD - a1) + (MOD - a2na3iimag)) * irot3.val();
                    }

                    if (s + 1 != (1 << (len - 2)))
                        irot *= info.irate3[LsbIndex(~(u32)(s))];
                }

                len -= 2;
            }
        }
    }

};

} // namespace nachia

namespace nachia {

template<class Elem, class NttInst = NttFromAcl<Elem>>
struct FpsNtt {
public:
    using Fps = FpsNtt;
    using ElemTy = Elem;
    static constexpr unsigned MOD = Elem::mod();
    static constexpr int CONV_THRES = 30;
    static const NttInst nttInst;
    static const unsigned zeta = nachia::PrimitiveRoot<MOD>::GetVal();
private:
    static Elem ZeroElem() noexcept {
        return Elem(0);
    }
    static Elem OneElem() noexcept {
        return Elem(1);
    }
    static Comb<Elem> comb;
    std::vector<Elem> a;
    int RSZ(int &sz) const {
        return sz = (sz < 0 ? size() : sz);
    }
public:

    int size() const noexcept {
        return a.size();
    }
    Elem &operator[](int x) noexcept {
        return a[x];
    }
    const Elem &operator[](int x) const noexcept {
        return a[x];
    }
    Elem getCoeff(int x) const noexcept {
        return (0 <= x && x < size()) ? a[x] : ZeroElem();
    }
    static Comb<Elem> &GetComb() {
        return comb;
    }
    static int BestNttSize(int x) noexcept {
        assert(x);
        return 1 << MsbIndex(x * 2 - 1);
    }
    Fps move() {
        return std::move(*this);
    }
    Fps &set(int i, Elem c) {
        a[i] = c;
        return *this;
    }

    Fps &removeLeadingZeros() {
        int newsz = size();

        while (newsz && a[newsz - 1].val() == 0)
            newsz--;

        a.resize(newsz);

        if ((int)a.capacity() / 4 > newsz)
            a.shrink_to_fit();

        return *this;
    }

    FpsNtt() {}
    FpsNtt(int sz) : a(sz, ZeroElem()) {}
    FpsNtt(int sz, Elem e) : a(sz, e) {}
    FpsNtt(std::vector<Elem> &&src) : a(std::move(src)) {}
    FpsNtt(const std::vector<Elem> &src) : a(src) {}

    Fps &ntt() {
        capSize(BestNttSize(size()));
        nttInst.Butterfly(a.begin(), size());
        return *this;
    }
    Fps &intt() {
        nttInst.IButterfly(a.begin(), a.size());
        return times(Elem::raw(size()).inv());
    }
    Fps clip(int srcL, int srcR = -1, int destL = 0, int resSz = -1) const {
        srcR = RSZ(srcR);

        if (resSz < 0)
            resSz = destL + srcR - srcL;

        int rj = std::min(std::min(srcR, size()) - srcL, resSz - destL);
        Fps res(resSz);

        for (int j = std::max(0u, -srcL); j < rj; j++)
            res[j + destL] = a[j + srcL];

        return res;
    }
    Fps clip() const {
        return *this;
    }

    Fps &capSize(int l, int r) {
        if (r <= (int)size())
            a.resize(r);

        if (size() <= l)
            a.resize(l, ZeroElem());

        return *this;
    }
    Fps &capSize(int z) {
        a.resize(RSZ(z), ZeroElem());
        return *this;
    }
    Fps &times(Elem x) {
        for (int i = 0; i < size(); i++) {
            a[i] *= x;
        }

        return *this;
    }
    Fps &clrRange(int l, int r) {
        for (int i = l; i < r; i++) {
            a[i] = ZeroElem();
        }

        return *this;
    }
    Fps &negate() {
        for (auto &e : a) {
            e = -e;
        }

        return *this;
    }
    Fps &mulEach(const Fps &other, int maxi = -1) {
        maxi = std::min(RSZ(maxi), std::min(size(), other.size()));

        for (int i = 0; i < maxi; i++)
            a[i] *= other[i];

        return *this;
    }
    Fps &reverse(int sz = -1) {
        RSZ(sz);
        std::reverse(a.begin(), a.begin() + sz);
        return *this;
    }

    static Fps convolution(const Fps &a, const Fps &b, int sz = -1) {
        if (std::min(a.size(), b.size()) <= CONV_THRES) {
            if (a.size() > b.size())
                return convolution(b, a, sz);

            if (sz < 0)
                sz = std::max(0u, a.size() + b.size() - 1);

            std::vector<Elem> res(sz);

            for (int i = 0; i < a.size(); i++)
                for (int j = 0; j < b.size() && i + j < sz; j++)
                    res[i + j] += a[i] * b[j];

            return res;
        }

        int Z = BestNttSize(a.size() + b.size() - 1);
        return a.clip(0, Z).ntt().mulEach(b.clip(0, Z).ntt()).intt().capSize(sz).move();
    }
    Fps convolve(const Fps &r, int sz = -1) const {
        return convolution(*this, r, sz);
    }
    Fps powerSum(int sz) const {
        RSZ(sz);

        if (sz == 0)
            return {};

        int q = std::min(sz, 32u);

        Fps x = Fps(q).set(0, OneElem()).move();

        for (int i = 1; i < q; i++)
            for (int j = 1; j <= std::min(i, (int)a.size() - 1); j++)
                x[i] += x[i - j] * a[j];

        while (x.size() < sz) {
            int hN = x.size(), N = hN * 2;
            Fps a = x.clip(0, N).ntt().move();
            Fps b = clip(0, N).ntt().mulEach(a).intt().clrRange(0, hN).ntt().mulEach(a).intt().move();

            for (int i = 0; i < hN; i++)
                b[i] = x[i];

            std::swap(b, x);
        }

        return x.capSize(sz).move();
    }

    Fps inv(int sz = -1) const {
        RSZ(sz);
        Elem iA0 = a[0].inv();
        return clip(0, std::min(sz, size())).times(-iA0).set(0, ZeroElem()).powerSum(sz).times(iA0).move();
    }

    Fps &difference() {
        if (size() == 0)
            return *this;

        for (int i = 0; i + 1 < size(); i++)
            a[i] = a[i + 1] * Elem::raw(i + 1);

        return capSize(size() - 1);
    }
    Fps &integral() {
        if (size() == 0)
            return capSize(1);

        capSize(size() + 1);
        comb.extend(size());

        for (int i = size() - 1; i >= 1; i--)
            a[i] = a[i - 1] * comb.invOf(i);

        return set(0, ZeroElem());
    }
    Fps log(int sz = -1) {
        RSZ(sz);
        assert(sz != 0);
        assert(a[0].val() == 1);
        return convolution(inv(sz), clip().difference(), sz - 1).integral();
    }

    Fps exp(int sz = -1) {
        RSZ(sz);
        Fps res = Fps(1).set(0, OneElem());

        while (res.size() < sz) {
            auto z = res.size();
            auto tmp = res.capSize(z * 2).log().set(0, -OneElem()).move();

            for (int i = 0; i < z * 2 && i < size(); i++)
                tmp[i] -= a[i];

            auto resntt = res.clip().ntt().mulEach(tmp.ntt()).intt().move();

            for (int i = z; i < z * 2; i++)
                res[i] = -resntt[i];
        }

        return res.capSize(0, sz).move();
    }

    Fps pow(unsigned long long k, int sz = -1) {
        int n = RSZ(sz);

        if (k == 0)
            return Fps(n).set(0, OneElem()).move();

        int ctz = 0;

        while (ctz < n && a[ctz].val() == 0)
            ctz++;

        if ((unsigned long long)ctz >= (n - 1) / k + 1)
            return Fps(n);

        Elem a0 = a[ctz];
        return clip(ctz, ctz + n - ctz * k).times(a0.inv()).log().times(Elem(k)).exp().times(a0.pow(k)).clip(0, -1,
                ctz * k);
    }

    auto begin() {
        return a.begin();
    }
    auto end() {
        return a.end();
    }
    auto begin() const {
        return a.begin();
    }
    auto end() const {
        return a.end();
    }

    std::string toString(std::string beg = "[ ", std::string delim = " ", std::string en = " ]") const {
        std::string res = beg;
        bool f = false;

        for (auto x : a) {
            if (f) {
                res += delim;
            }

            f = true;
            res += std::to_string(x.val());
        }

        res += en;
        return res;
    }

    std::vector<Elem> getVectorMoved() {
        return std::move(a);
    }

    Fps &operator+=(const Fps &r) {
        capSize(std::max(size(), r.size()));

        for (int i = 0; i < r.size(); i++)
            a[i] += r[i];

        return *this;
    }
    Fps &operator-=(const Fps &r) {
        capSize(std::max(size(), r.size()));

        for (int i = 0; i < r.size(); i++)
            a[i] -= r[i];

        return *this;
    }
    Fps operator+(const Fps &r) const {
        return (clip(0, std::max(size(), r.size())) += r).move();
    }
    Fps operator-(const Fps &r) const {
        return (clip(0, std::max(size(), r.size())) -= r).move();
    }
    Fps operator-() const {
        return (clip().negate()).move();
    }
    Fps operator*(const Fps &r) const {
        return convolve(r).removeLeadingZeros().move();
    }
    Fps &operator*=(const Fps &r) {
        return (*this) = operator*(r);
    }
    Fps &operator*=(Elem m) {
        return times(m);
    }
    Fps operator*(Elem m) const {
        return (clip() *= m).move();
    }

    Elem eval(Elem x) const {
        Elem res = 0;

        for (int i = size() - 1; i >= 0; i--)
            res = res * x + a[i];

        return res;
    }
};

template<class Elem, class NttInst> Comb<Elem> FpsNtt<Elem, NttInst>::comb;
template<class Elem, class NttInst> const NttInst FpsNtt<Elem, NttInst>::nttInst;

} // namespace nachia


namespace nachia {

template<class Fps>
std::vector<typename Fps::ElemTy> FpsSampleCoefficientOfPower(Fps f, Fps g, int maxPower, int coeffAt) {
    using Modint = typename Fps::ElemTy;
    Modint Zero = Modint(0);
    Modint One = Modint(1);
    int n = 1;

    while (n < std::max(coeffAt + 1, maxPower + 1))
        n *= 2;

    n *= 2;
    auto q = f.clip(0, n / 2, 0, n * 2);
    q.negate();
    auto p = g.clip(0, n / 2, 0, n * 2);
    int d = n / 2;

    while (d != 1) {
        auto qn = q.clip(0, n, d * 2, n * 2);

        for (int i = 1; i < n + d * 2; i += 2)
            qn[i] = -qn[i];

        d /= 2;
        qn[0] = One;
        auto qnntt = qn.clip(0, n * 2).ntt().move();
        p.ntt().mulEach(qnntt).intt();
        int f = coeffAt % 2;

        for (int i = 0; i < n; i += d * 2) {
            for (int j = 0; j < d; j++)
                p[i + j] = p[i * 2 + j * 2 + f];

            for (int j = d; j < d * 2; j++)
                p[i + j] = Zero;
        }

        for (int i = n; i < n * 2; i++)
            p[i] = Zero;

        q.ntt().mulEach(qnntt).intt();

        for (int i = 0; i < n; i += d * 2) {
            for (int j = 0; j < d; j++)
                q[i + j] = q[i * 2 + j * 2];

            for (int j = d; j < d * 2; j++)
                q[i + j] = Zero;
        }

        for (int i = 0; i < n / 2; i += d * 2)
            for (int j = 0; j < d; j++)
                q[i + j] += qn[i * 2 + j * 2 + d * 4];

        for (int i = n; i < n * 2; i++)
            q[i] = Zero;

        coeffAt /= 2;
    }

    n /= 2;

    for (int i = 0; i < n; i++)
        p[i] = p[i * 2];

    if (f[0].val() != 0) {
        for (int i = 0; i < n; i++)
            q[i] = q[i * 2];

        return (p.clip(0, n) * q.clip(0, n, 1, n + 1).set(0, One).inv(n)).clip(0, maxPower + 1).getVectorMoved();
    }

    return p.clip(0, maxPower + 1).getVectorMoved();
}

}
namespace nachia {

template<class Fps>
Fps CompositionalInverseOfFps(int N, Fps f) {
    if (N <= 1)
        return Fps(N);

    using Elem = typename Fps::ElemTy;
    auto t = f[1].inv();
    f.times(t);
    Fps g = FpsSampleCoefficientOfPower(f.clip(0, N), Fps(1).set(0, Elem(1)), N - 1, N - 1);
    auto comb = Fps::GetComb();
    comb.extend(N);
    auto K = Elem(N - 1);

    for (int i = 1; i < N; i++)
        g[i] *= K * comb.invOf(i);

    g = g.reverse(N).pow((-K).inv().val(), N);

    for (int i = N - 1; i >= 1; i--)
        g[i] = g[i - 1];

    auto tt = t;

    for (int i = 1; i < N; i++) {
        g[i] *= tt;
        tt *= t;
    }

    g[0] = Elem(0);
    return g;
}

}
namespace nachia {
std::pair<long long, long long> ExtGcd(long long a, long long b) {
    long long x = 1, y = 0;

    while (b) {
        long long u = a / b;
        std::swap(a -= b * u, b);
        std::swap(x -= y * u, y);
    }

    return std::make_pair(x, a);
}

} // namespace nachia

namespace nachia {

template<unsigned MOD>
struct StaticModint {
private:
    unsigned x;
public:

    using my_type = StaticModint;
    template< class Elem >
    static Elem safe_mod(Elem x) {
        if (x < 0) {
            if (0 <= x + MOD)
                return x + MOD;

            return MOD - ((-(x + MOD) - 1) % MOD + 1);
        }

        return x % MOD;
    }

    StaticModint() : x(0) {}
    StaticModint(const my_type &a) : x(a.x) {}
    StaticModint &operator=(const my_type &) = default;
    template< class Elem > StaticModint(Elem v) : x(safe_mod(v)) {}
    unsigned operator*() const noexcept {
        return x;
    }
    my_type &operator+=(const my_type &r) noexcept {
        auto t = x + r.x;

        if (t >= MOD)
            t -= MOD;

        x = t;
        return *this;
    }
    my_type operator+(const my_type &r) const noexcept {
        my_type res = *this;
        return res += r;
    }
    my_type &operator-=(const my_type &r) noexcept {
        auto t = x + MOD - r.x;

        if (t >= MOD)
            t -= MOD;

        x = t;
        return *this;
    }
    my_type operator-(const my_type &r) const noexcept {
        my_type res = *this;
        return res -= r;
    }
    my_type operator-() const noexcept {
        my_type res = *this;
        res.x = ((res.x == 0) ? 0 : (MOD - res.x));
        return res;
    }
    my_type &operator*=(const my_type &r)noexcept {
        x = (u64)x * r.x % MOD;
        return *this;
    }
    my_type operator*(const my_type &r) const noexcept {
        my_type res = *this;
        return res *= r;
    }
    my_type pow(unsigned long long i) const noexcept {
        my_type a = *this, res = 1;

        while (i) {
            if (i & 1) {
                res *= a;
            }

            a *= a;
            i >>= 1;
        }

        return res;
    }
    my_type inv() const {
        return my_type(ExtGcd(x, MOD).first);
    }
    unsigned val() const noexcept {
        return x;
    }
    static constexpr unsigned mod() {
        return MOD;
    }
    static my_type raw(unsigned val) noexcept {
        auto res = my_type();
        res.x = val;
        return res;
    }
    my_type &operator/=(const my_type &r) {
        return operator*=(r.inv());
    }
    my_type operator/(const my_type &r) const {
        return operator*(r.inv());
    }
};

}

namespace nachia {

struct CInStream {
private:
    static const unsigned INPUT_BUF_SIZE = 1 << 17;
    unsigned p = INPUT_BUF_SIZE;
    static char Q[INPUT_BUF_SIZE];
public:
    using MyType = CInStream;
    char seekChar() {
        if (p == INPUT_BUF_SIZE) {
            size_t len = fread(Q, 1, INPUT_BUF_SIZE, stdin);

            if (len != INPUT_BUF_SIZE)
                Q[len] = '\0';

            p = 0;
        }

        return Q[p];
    }
    void skipSpace() {
        while (isspace(seekChar()))
            p++;
    }
private:
    template<class T, int sp = 1>
    T nextUInt() {
        if constexpr(sp)
            skipSpace();

        T buf = 0;

        while (true) {
            char tmp = seekChar();

            if ('9' < tmp || tmp < '0')
                break;

            buf = buf * 10 + (tmp - '0');
            p++;
        }

        return buf;
    }
public:
    uint32_t nextU32() {
        return nextUInt<uint32_t>();
    }
    int32_t nextI32() {
        skipSpace();

        if (seekChar() == '-') {
            p++;
            return (int32_t)(-nextUInt<uint32_t, 0>());
        }

        return (int32_t)nextUInt<uint32_t, 0>();
    }
    uint64_t nextU64() {
        return nextUInt<uint64_t>();
    }
    int64_t nextI64() {
        skipSpace();

        if (seekChar() == '-') {
            p++;
            return (int64_t)(-nextUInt<int64_t, 0>());
        }

        return (int64_t)nextUInt<int64_t, 0>();
    }
    template<class T>
    T nextInt() {
        skipSpace();

        if (seekChar() == '-') {
            p++;
            return - nextUInt<T, 0>();
        }

        return nextUInt<T, 0>();
    }
    char nextChar() {
        skipSpace();
        char buf = seekChar();
        p++;
        return buf;
    }
    std::string nextToken() {
        skipSpace();
        std::string buf;

        while (true) {
            char ch = seekChar();

            if (isspace(ch) || ch == '\0')
                break;

            buf.push_back(ch);
            p++;
        }

        return buf;
    }
    MyType &operator>>(unsigned &dest) {
        dest = nextU32();
        return *this;
    }
    MyType &operator>>(unsigned long &dest) {
        dest = nextU64();
        return *this;
    }
    MyType &operator>>(long &dest) {
        dest = nextI64();
        return *this;
    }
    MyType &operator>>(unsigned long long &dest) {
        dest = nextU64();
        return *this;
    }
    MyType &operator>>(long long &dest) {
        dest = nextI64();
        return *this;
    }
    MyType &operator>>(std::string &dest) {
        dest = nextToken();
        return *this;
    }
    MyType &operator>>(char &dest) {
        dest = nextChar();
        return *this;
    }
} cin;

struct FastOutputTable {
    char LZ[1000][4] = {};
    char NLZ[1000][4] = {};
    constexpr FastOutputTable() {
        using u32 = uint_fast32_t;

        for (u32 d = 0; d < 1000; d++) {
            LZ[d][0] = ('0' + d / 100 % 10);
            LZ[d][1] = ('0' + d /  10 % 10);
            LZ[d][2] = ('0' + d /   1 % 10);
            LZ[d][3] = '\0';
        }

        for (u32 d = 0; d < 1000; d++) {
            u32 i = 0;

            if (d >= 100)
                NLZ[d][i++] = ('0' + d / 100 % 10);

            if (d >=  10)
                NLZ[d][i++] = ('0' + d /  10 % 10);

            if (d >=   1)
                NLZ[d][i++] = ('0' + d /   1 % 10);

            NLZ[d][i++] = '\0';
        }
    }
};

struct COutStream {
private:
    using u32 = uint32_t;
    using u64 = uint64_t;
    using MyType = COutStream;
    static const u32 OUTPUT_BUF_SIZE = 1 << 17;
    static char Q[OUTPUT_BUF_SIZE];
    static constexpr FastOutputTable TB = FastOutputTable();
    u32 p = 0;
    static constexpr u32 P10(u32 d) {
        return d ? P10(d - 1) * 10 : 1;
    }
    static constexpr u64 P10L(u32 d) {
        return d ? P10L(d - 1) * 10 : 1;
    }
    template<class T, class U> static void Fil(T &m, U &l, U x) {
        m = l / x;
        l -= m * x;
    }
public:
    void next_dig9(u32 x) {
        u32 y;
        Fil(y, x, P10(6));
        nextCstr(TB.LZ[y]);
        Fil(y, x, P10(3));
        nextCstr(TB.LZ[y]);
        nextCstr(TB.LZ[x]);
    }
    void nextChar(char c) {
        Q[p++] = c;

        if (p == OUTPUT_BUF_SIZE) {
            fwrite(Q, p, 1, stdout);
            p = 0;
        }
    }
    void nextEoln() {
        nextChar('\n');
    }
    void nextCstr(const char *s) {
        while (*s)
            nextChar(*(s++));
    }
    void nextU32(uint32_t x) {
        u32 y = 0;

        if (x >= P10(9)) {
            Fil(y, x, P10(9));
            nextCstr(TB.NLZ[y]);
            next_dig9(x);
        } else if (x >= P10(6)) {
            Fil(y, x, P10(6));
            nextCstr(TB.NLZ[y]);
            Fil(y, x, P10(3));
            nextCstr(TB.LZ[y]);
            nextCstr(TB.LZ[x]);
        } else if (x >= P10(3)) {
            Fil(y, x, P10(3));
            nextCstr(TB.NLZ[y]);
            nextCstr(TB.LZ[x]);
        } else if (x >= 1)
            nextCstr(TB.NLZ[x]);
        else
            nextChar('0');
    }
    void nextI32(int32_t x) {
        if (x >= 0)
            nextU32(x);
        else {
            nextChar('-');
            nextU32((u32) - x);
        }
    }
    void nextU64(uint64_t x) {
        u32 y = 0;

        if (x >= P10L(18)) {
            Fil(y, x, P10L(18));
            nextU32(y);
            Fil(y, x, P10L(9));
            next_dig9(y);
            next_dig9(x);
        } else if (x >= P10L(9)) {
            Fil(y, x, P10L(9));
            nextU32(y);
            next_dig9(x);
        } else
            nextU32(x);
    }
    void nextI64(int64_t x) {
        if (x >= 0)
            nextU64(x);
        else {
            nextChar('-');
            nextU64((u64) - x);
        }
    }
    template<class T>
    void nextInt(T x) {
        if (x < 0) {
            nextChar('-');
            x = -x;
        }

        if (!(0 < x)) {
            nextChar('0');
            return;
        }

        std::string buf;

        while (0 < x) {
            buf.push_back('0' + (int)(x % 10));
            x /= 10;
        }

        for (int i = (int)buf.size() - 1; i >= 0; i--) {
            nextChar(buf[i]);
        }
    }
    void writeToFile(bool flush = false) {
        fwrite(Q, p, 1, stdout);

        if (flush)
            fflush(stdout);

        p = 0;
    }
    COutStream() {
        Q[0] = 0;
    }
    ~COutStream() {
        writeToFile();
    }
    MyType &operator<<(unsigned tg) {
        nextU32(tg);
        return *this;
    }
    MyType &operator<<(unsigned long tg) {
        nextU64(tg);
        return *this;
    }
    MyType &operator<<(unsigned long long tg) {
        nextU64(tg);
        return *this;
    }
    MyType &operator<<(long tg) {
        nextI64(tg);
        return *this;
    }
    MyType &operator<<(long long tg) {
        nextI64(tg);
        return *this;
    }
    MyType &operator<<(const std::string &tg) {
        nextCstr(tg.c_str());
        return *this;
    }
    MyType &operator<<(const char *tg) {
        nextCstr(tg);
        return *this;
    }
    MyType &operator<<(char tg) {
        nextChar(tg);
        return *this;
    }
} cout;

char CInStream::Q[INPUT_BUF_SIZE];
char COutStream::Q[OUTPUT_BUF_SIZE];

}

main() {
    using nachia::cin; using nachia::cout; using Modint = nachia::StaticModint<998244353>; using Fps = nachia::FpsNtt<Modint>;
    auto nextInt = []() -> int { int a; cin >> a; return a; };

    int N = nextInt();
    Fps a(N);

    for (u32 i = 0; i < N; i++)
        a[i] = Modint::raw(nextInt());

    Fps b = nachia::CompositionalInverseOfFps(N, a.move());
    cout << b.toString("", " ", "\n");
}