// drkenさんのgithubより引用
// https://github.com/drken1215/algorithm/blob/master/MathAlgebra/composition_formal_power_series.cpp

//
// FPS の合成 (Kinoshita-Li 法, O(N (log N)^2))
//
// verified:
//   Yosupo Library Checker - Composition of Formal Power Series (Large)
//     https://judge.yosupo.jp/problem/composition_of_formal_power_series_large
//

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

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

//------------------------------//
// mod algorithms
//------------------------------//

// modint
template <int MOD = 998244353, bool PRIME = true>
struct Fp {
    // inner value
    unsigned int val;

    // constructor
    constexpr Fp() : val(0) {}
    template <std::signed_integral T>
    constexpr Fp(T v) {
        long long tmp = (long long)(v % (long long)(get_umod()));
        if (tmp < 0)
            tmp += get_umod();
        val = (unsigned int)(tmp);
    }
    template <std::unsigned_integral T>
    constexpr Fp(T v) {
        val = (unsigned int)(v % get_umod());
    }
    constexpr long long get() const { return val; }
    constexpr static int get_mod() { return MOD; }
    constexpr static unsigned int get_umod() { return MOD; }

    // arithmetic operators
    constexpr Fp operator+() const { return Fp(*this); }
    constexpr Fp operator-() const { return Fp() - Fp(*this); }
    constexpr Fp operator+(const Fp &r) const { return Fp(*this) += r; }
    constexpr Fp operator-(const Fp &r) const { return Fp(*this) -= r; }
    constexpr Fp operator*(const Fp &r) const { return Fp(*this) *= r; }
    constexpr Fp operator/(const Fp &r) const { return Fp(*this) /= r; }
    constexpr Fp &operator+=(const Fp &r) {
        val += r.val;
        if (val >= get_umod())
            val -= get_umod();
        return *this;
    }
    constexpr Fp &operator-=(const Fp &r) {
        val -= r.val;
        if (val >= get_umod())
            val += get_umod();
        return *this;
    }
    constexpr Fp &operator*=(const Fp &r) {
        unsigned long long tmp = val;
        tmp *= r.val;
        val = (unsigned int)(tmp % get_umod());
        return *this;
    }
    constexpr Fp &operator/=(const Fp &r) {
        return *this = *this * r.inv();
    }
    constexpr Fp pow(long long n) const {
        assert(n >= 0);
        Fp res(1), mul(*this);
        while (n) {
            if (n & 1)
                res *= mul;
            mul *= mul;
            n >>= 1;
        }
        return res;
    }
    constexpr Fp inv() const {
        assert(val);
        if (PRIME) {
            return pow(get_umod() - 2);
        } else {
            assert(gcd(val, get_umod()) == 1);
            long long m = get_umod(), a = val, b = m, u = 1, v = 0;
            while (b > 0) {
                auto t = a / b;
                a -= t * b, swap(a, b);
                u -= t * v, swap(u, v);
            }
            return Fp(u);
        }
    }

    // other operators
    constexpr bool operator==(const Fp &r) const {
        return this->val == r.val;
    }
    constexpr bool operator!=(const Fp &r) const {
        return this->val != r.val;
    }
    constexpr bool operator<(const Fp &r) const {
        return this->val < r.val;
    }
    constexpr bool operator>(const Fp &r) const {
        return this->val > r.val;
    }
    constexpr bool operator<=(const Fp &r) const {
        return this->val <= r.val;
    }
    constexpr bool operator>=(const Fp &r) const {
        return this->val >= r.val;
    }
    constexpr Fp &operator++() {
        ++val;
        if (val == get_umod())
            val = 0;
        return *this;
    }
    constexpr Fp &operator--() {
        if (val == 0)
            val = get_umod();
        --val;
        return *this;
    }
    constexpr Fp operator++(int) {
        Fp res = *this;
        ++*this;
        return res;
    }
    constexpr Fp operator--(int) {
        Fp res = *this;
        --*this;
        return res;
    }
    friend constexpr istream &operator>>(istream &is, Fp &x) {
        long long tmp = 1;
        is >> tmp;
        tmp = tmp % (long long)(get_umod());
        if (tmp < 0)
            tmp += get_umod();
        x.val = (unsigned int)(tmp);
        return is;
    }
    friend constexpr ostream &operator<<(ostream &os, const Fp &x) {
        return os << x.val;
    }
    friend constexpr Fp pow(const Fp &r, long long n) {
        return r.pow(n);
    }
    friend constexpr Fp inv(const Fp &r) {
        return r.inv();
    }
};

// Binomial coefficient
template <class mint>
struct BiCoef {
    vector<mint> fact_, inv_, finv_;
    constexpr BiCoef() {}
    constexpr BiCoef(int n) : fact_(n, 1), inv_(n, 1), finv_(n, 1) {
        init(n);
    }
    constexpr void init(int n) {
        fact_.assign(n, 1), inv_.assign(n, 1), finv_.assign(n, 1);
        int MOD = fact_[0].get_mod();
        for (int i = 2; i < n; i++) {
            fact_[i] = fact_[i - 1] * i;
            inv_[i] = -inv_[MOD % i] * (MOD / i);
            finv_[i] = finv_[i - 1] * inv_[i];
        }
    }
    constexpr mint com(int n, int k) const {
        if (n < k || n < 0 || k < 0)
            return 0;
        return fact_[n] * finv_[k] * finv_[n - k];
    }
    constexpr mint fact(int n) const {
        if (n < 0)
            return 0;
        return fact_[n];
    }
    constexpr mint inv(int n) const {
        if (n < 0)
            return 0;
        return inv_[n];
    }
    constexpr mint finv(int n) const {
        if (n < 0)
            return 0;
        return finv_[n];
    }
};

//------------------------------//
// NTT
//------------------------------//

// calc primitive root
constexpr int calc_primitive_root(long long m) {
    if (m == 1)
        return -1;
    if (m == 2)
        return 1;
    if (m == 998244353)
        return 3;
    if (m == 167772161)
        return 3;
    if (m == 469762049)
        return 3;
    if (m == 754974721)
        return 11;
    if (m == 645922817)
        return 3;
    if (m == 897581057)
        return 3;

    auto mod_pow = [&](long long a, long long n, long long m) {
        long long res = 1;
        while (n > 0) {
            if (n % 2 == 1)
                res = res * a % m;
            a = a * a % m;
            n >>= 1;
        }
        return res;
    };
    long long divs[20] = {};
    divs[0] = 2;
    long long cnt = 1;
    long long x = (m - 1) / 2;
    while (x % 2 == 0)
        x /= 2;
    for (long long i = 3; i * i <= x; i += 2) {
        if (x % i == 0) {
            divs[cnt++] = i;
            while (x % i == 0)
                x /= i;
        }
    }
    if (x > 1)
        divs[cnt++] = x;
    for (long long g = 2;; g++) {
        bool ok = true;
        for (int i = 0; i < cnt; i++) {
            if (mod_pow(g, (m - 1) / divs[i], m) == 1) {
                ok = false;
                break;
            }
        }
        if (ok)
            return g;
    }
}

// NTT setup
template <class mint, int MOD = mint::get_mod(), int g = calc_primitive_root(mint::get_mod())>
struct ntt_setup {
    static constexpr int bsf_constexpr(unsigned int x) {
        int i = 0;
        while (!(x & (1 << i)))
            i++;
        return i;
    };

    static constexpr int rank = bsf_constexpr(MOD - 1);
    array<mint, rank + 1> root, iroot; // root[i]^(2^i) = 1, root[i] * iroot[i] = 1
    array<mint, max(0, rank - 1)> rate2, irate2;
    array<mint, max(0, rank - 2)> rate3, irate3;

    ntt_setup() {
        root[rank] = mint(g).pow((MOD - 1) >> rank);
        iroot[rank] = root[rank].inv();
        for (int i = rank - 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 (int i = 0; i < rank - 1; i++) {
            rate2[i] = root[i + 2] * prod;
            irate2[i] = iroot[i + 2] * iprod;
            prod *= iroot[i + 2];
            iprod *= root[i + 2];
        }
        prod = 1, iprod = 1;
        for (int i = 0; i < rank - 2; i++) {
            rate3[i] = root[i + 3] * prod;
            irate3[i] = iroot[i + 3] * iprod;
            prod *= iroot[i + 3];
            iprod *= root[i + 3];
        }
    }
};

// NTT transformation
template <class mint, int MOD = mint::get_mod()>
void ntt_trans(vector<mint> &v) {
    int n = (int)v.size();
    int h = 0;
    while ((1U << h) < (unsigned int)(n))
        h++;
    static const ntt_setup<mint> setup;

    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 = v[i + offset];
                    auto r = v[i + offset + p] * rot;
                    v[i + offset] = l + r;
                    v[i + offset + p] = l - r;
                }
                if (s + 1 != (1 << len)) {
                    rot *= setup.rate2[setup.bsf_constexpr(~(unsigned int)(s))];
                }
            }
            len++;
        } else {
            int p = 1 << (h - len - 2);
            mint rot = 1, imag = setup.root[2];
            for (int s = 0; s < (1 << len); s++) {
                mint rot2 = rot * rot, rot3 = rot2 * rot;
                int offset = s << (h - len);
                for (int i = 0; i < p; i++) {
                    auto mod2 = 1ULL * MOD * MOD;
                    auto a0 = 1ULL * v[i + offset].val;
                    auto a1 = 1ULL * v[i + offset + p].val * rot.val;
                    auto a2 = 1ULL * v[i + offset + p * 2].val * rot2.val;
                    auto a3 = 1ULL * v[i + offset + p * 3].val * rot3.val;
                    auto tmp = 1ULL * mint(a1 + mod2 - a3).val * imag.val;
                    auto na2 = mod2 - a2;
                    v[i + offset] = a0 + a2 + a1 + a3;
                    v[i + offset + p] = a0 + a2 + (mod2 * 2 - (a1 + a3));
                    v[i + offset + p * 2] = a0 + na2 + tmp;
                    v[i + offset + p * 3] = a0 + na2 + (mod2 - tmp);
                }
                if (s + 1 != (1 << len)) {
                    rot *= setup.rate3[setup.bsf_constexpr(~(unsigned int)(s))];
                }
            }
            len += 2;
        }
    }
}

// NTT inv-transformation
template <class mint, int MOD = mint::get_mod()>
void ntt_trans_inv(vector<mint> &v) {
    int n = (int)v.size();
    int h = 0;
    while ((1U << h) < (unsigned int)(n))
        h++;
    static const ntt_setup<mint> setup;

    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 = v[i + offset];
                    auto r = v[i + offset + p];
                    v[i + offset] = l + r;
                    v[i + offset + p] = (unsigned long long)((long long)(MOD) + l.val - r.val) * irot.val;
                }
                if (s + 1 != (1 << (len - 1))) {
                    irot *= setup.irate2[setup.bsf_constexpr(~(unsigned int)(s))];
                }
            }
            len--;
        } else {
            int p = 1 << (h - len);
            mint irot = 1, iimag = setup.iroot[2];
            for (int s = 0; s < (1 << (len - 2)); s++) {
                mint irot2 = irot * irot, irot3 = irot2 * irot;
                int offset = s << (h - len + 2);
                for (int i = 0; i < p; i++) {
                    auto a0 = 1ULL * v[i + offset].val;
                    auto a1 = 1ULL * v[i + offset + p].val;
                    auto a2 = 1ULL * v[i + offset + p * 2].val;
                    auto a3 = 1ULL * v[i + offset + p * 3].val;
                    auto tmp = 1ULL * mint((MOD + a2 - a3) * iimag.val).val;
                    v[i + offset] = a0 + a1 + a2 + a3;
                    v[i + offset + p] = (a0 + (MOD - a1) + tmp) * irot.val;
                    v[i + offset + p * 2] = (a0 + a1 + (MOD - a2) + (MOD - a3)) * irot2.val;
                    v[i + offset + p * 3] = (a0 + (MOD - a1) + (MOD - tmp)) * irot3.val;
                }
                if (s + 1 != (1 << (len - 2))) {
                    irot *= setup.irate3[setup.bsf_constexpr(~(unsigned int)(s))];
                }
            }
            len -= 2;
        }
    }
    mint in = mint(n).inv();
    for (int i = 0; i < n; i++)
        v[i] *= in;
}

// naive convolution
template <class VEC>
VEC convolution_naive(const VEC &a, const VEC &b) {
    int n = (int)a.size(), m = (int)b.size();
    if (!n || !m)
        return {};
    VEC res(n + m - 1);
    if (n < m) {
        for (int j = 0; j < m; j++)
            for (int i = 0; i < n; i++)
                res[i + j] += a[i] * b[j];
    } else {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                res[i + j] += a[i] * b[j];
    }
    return res;
}

// ntt convolution
template <class mint>
vector<mint> convolution_ntt(vector<mint> a, vector<mint> b) {
    int MOD = mint::get_mod();
    int n = (int)a.size(), m = (int)b.size();
    if (!n || !m)
        return {};
    int z = (int)bit_ceil((unsigned int)(n + m - 1));
    assert((MOD - 1) % z == 0);
    a.resize(z), b.resize(z);
    ntt_trans(a), ntt_trans(b);
    for (int i = 0; i < z; i++)
        a[i] *= b[i];
    ntt_trans_inv(a);
    a.resize(n + m - 1);
    return a;
}

// convolution long long (if u64 is necessary, use convolution_ull)
template <class VEC>
VEC convolution_ll(const VEC &a, const VEC &b) {
    int n = (int)a.size(), m = (int)b.size();
    if (!n || !m)
        return VEC();
    if (min(n, m) <= 60)
        return convolution_naive(a, b);

    static constexpr int MOD0 = 754974721; // 2^24
    static constexpr int MOD1 = 167772161; // 2^25
    static constexpr int MOD2 = 469762049; // 2^26
    using mint0 = Fp<MOD0>;
    using mint1 = Fp<MOD1>;
    using mint2 = Fp<MOD2>;
    static const mint1 imod0 = 95869806;   // modinv(MOD0, MOD1);
    static const mint2 imod1 = 104391568;  // modinv(MOD1, MOD2);
    static const mint2 imod01 = 187290749; // imod1 / MOD0;

    vector<mint0> a0(n, 0), b0(m, 0);
    vector<mint1> a1(n, 0), b1(m, 0);
    vector<mint2> a2(n, 0), b2(m, 0);
    for (int i = 0; i < n; ++i)
        a0[i] = a[i], a1[i] = a[i], a2[i] = a[i];
    for (int i = 0; i < m; ++i)
        b0[i] = b[i], b1[i] = b[i], b2[i] = b[i];
    auto c0 = convolution_ntt(std::move(a0), std::move(b0));
    auto c1 = convolution_ntt(std::move(a1), std::move(b1));
    auto c2 = convolution_ntt(std::move(a2), std::move(b2));

    VEC res(n + m - 1);
    long long mod0 = MOD0, mod01 = mod0 * MOD1;
    for (int i = 0; i < n + m - 1; ++i) {
        unsigned int y0 = c0[i].val;
        unsigned int y1 = (imod0 * (c1[i] - mint1(y0))).val;
        unsigned int y2 = (imod01 * (c2[i] - mint2(y0)) - imod1 * y1).val;
        res[i] = mod01 * y2 + mod0 * y1 + y0;
    }
    return res;
}

// convolution in general mod
template <class mint>
vector<mint> convolution_general_mod(const vector<mint> &a, const vector<mint> &b) {
    int n = (int)a.size(), m = (int)b.size();
    if (!n || !m)
        return {};
    if (min(n, m) <= 60)
        return convolution_naive(a, b);
    if constexpr (std::is_same_v<mint, Fp<998244353>>)
        return convolution_ntt(a, b);

    static constexpr int MOD0 = 754974721; // 2^24
    static constexpr int MOD1 = 167772161; // 2^25
    static constexpr int MOD2 = 469762049; // 2^26
    using mint0 = Fp<MOD0>;
    using mint1 = Fp<MOD1>;
    using mint2 = Fp<MOD2>;
    static const mint1 imod0 = 95869806;   // modinv(MOD0, MOD1);
    static const mint2 imod1 = 104391568;  // modinv(MOD1, MOD2);
    static const mint2 imod01 = 187290749; // imod1 / MOD0;

    vector<mint0> a0(n, 0), b0(m, 0);
    vector<mint1> a1(n, 0), b1(m, 0);
    vector<mint2> a2(n, 0), b2(m, 0);
    for (int i = 0; i < n; ++i)
        a0[i] = a[i].val, a1[i] = a[i].val, a2[i] = a[i].val;
    for (int i = 0; i < m; ++i)
        b0[i] = b[i].val, b1[i] = b[i].val, b2[i] = b[i].val;
    auto c0 = convolution_ntt(std::move(a0), std::move(b0));
    auto c1 = convolution_ntt(std::move(a1), std::move(b1));
    auto c2 = convolution_ntt(std::move(a2), std::move(b2));

    vector<mint> res(n + m - 1);
    mint mod0 = MOD0, mod01 = mod0 * MOD1;
    for (int i = 0; i < n + m - 1; ++i) {
        unsigned int y0 = c0[i].val;
        unsigned int y1 = (imod0 * (c1[i] - mint1(y0))).val;
        unsigned int y2 = (imod01 * (c2[i] - mint2(y0)) - imod1 * y1).val;
        res[i] = mod01 * y2 + mod0 * y1 + y0;
    }
    return res;
}

// convolution overall
template <class T>
vector<T> convolution(const vector<T> &a, const vector<T> &b) {
    int n = (int)a.size(), m = (int)b.size();
    if (!n || !m)
        return {};
    if (min(n, m) <= 60)
        return convolution_naive(a, b);
    if constexpr (std::is_same_v<T, Fp<998244353>>)
        return convolution_ntt(a, b);
    else if constexpr (std::is_integral_v<T>)
        return convolution_ll(a, b);
    else
        return convolution_general_mod(a, b);
}

//------------------------------//
// FPS
//------------------------------//

// Formal Power Series
template <class mint>
struct FPS : vector<mint> {
    static const int SPARSE_BOARDER = 60;
    using vector<mint>::vector;

    // constructor
    constexpr FPS(const vector<mint> &r) : vector<mint>(r) {}

    // core operator
    constexpr FPS pre(int siz) const {
        return FPS(begin(*this), begin(*this) + min((int)this->size(), siz));
    }
    constexpr FPS rev() const {
        FPS res = *this;
        reverse(begin(res), end(res));
        return res;
    }
    constexpr FPS &normalize() {
        while (!this->empty() && this->back() == 0)
            this->pop_back();
        return *this;
    }
    constexpr mint eval(const mint &v) const {
        mint res = 0;
        for (int i = (int)this->size() - 1; i >= 0; --i) {
            res *= v;
            res += (*this)[i];
        }
        return res;
    }
    constexpr int count_terms() const {
        int res = 0;
        for (int i = 0; i < (int)this->size(); i++)
            if ((*this)[i] != mint(0))
                res++;
        return res;
    }

    // basic operator
    constexpr FPS operator-() const noexcept {
        FPS res = (*this);
        for (int i = 0; i < (int)res.size(); ++i)
            res[i] = -res[i];
        return res;
    }
    constexpr FPS operator+(const mint &v) const { return FPS(*this) += v; }
    constexpr FPS operator+(const FPS &r) const { return FPS(*this) += r; }
    constexpr FPS operator-(const mint &v) const { return FPS(*this) -= v; }
    constexpr FPS operator-(const FPS &r) const { return FPS(*this) -= r; }
    constexpr FPS operator*(const mint &v) const { return FPS(*this) *= v; }
    constexpr FPS operator*(const FPS &r) const { return FPS(*this) *= r; }
    constexpr FPS operator/(const mint &v) const { return FPS(*this) /= v; }
    constexpr FPS operator/(const FPS &r) const { return FPS(*this) /= r; }
    constexpr FPS operator%(const FPS &r) const { return FPS(*this) %= r; }
    constexpr FPS operator<<(int x) const { return FPS(*this) <<= x; }
    constexpr FPS operator>>(int x) const { return FPS(*this) >>= x; }
    constexpr FPS &operator+=(const mint &v) {
        if (this->empty())
            this->reserve(1), this->resize(1);
        (*this)[0] += v;
        return *this;
    }
    constexpr FPS &operator+=(const FPS &r) {
        if (r.size() > this->size())
            this->reserve(r.size()), this->resize(r.size());
        for (int i = 0; i < (int)r.size(); ++i)
            (*this)[i] += r[i];
        return this->normalize();
    }
    constexpr FPS &operator-=(const mint &v) {
        if (this->empty())
            this->reserve(1), this->resize(1);
        (*this)[0] -= v;
        return *this;
    }
    constexpr FPS &operator-=(const FPS &r) {
        if (r.size() > this->size())
            this->reserve(r.size()), this->resize(r.size());
        for (int i = 0; i < (int)r.size(); ++i)
            (*this)[i] -= r[i];
        return this->normalize();
    }
    constexpr FPS &operator*=(const mint &v) {
        for (int i = 0; i < (int)this->size(); ++i)
            (*this)[i] *= v;
        return *this;
    }
    constexpr FPS &operator*=(const FPS &r) {
        return *this = convolution((*this), r);
    }
    constexpr FPS &divide_by_modint(const mint &v) {
        assert(v != 0);
        mint iv = v.inv();
        for (int i = 0; i < (int)this->size(); ++i)
            (*this)[i] *= iv;
        return *this;
    }
    constexpr FPS &divide_by_integer(const mint &v) {
        assert(v != 0);
        for (int i = 0; i < (int)this->size(); ++i)
            (*this)[i] /= v;
        return *this;
    }
    constexpr FPS &operator/=(const mint &v) {
        assert(v != 0);
        if constexpr (std::is_integral_v<mint>)
            return divide_by_integer(v);
        else
            return divide_by_modint(v);
    }

    // division, r must be normalized (r.back() must not be 0)
    constexpr FPS &operator/=(const FPS &r) {
        assert(!r.empty());
        assert(r.back() != 0);
        this->normalize();
        if (this->size() < r.size()) {
            this->clear();
            return *this;
        }
        int need = (int)this->size() - (int)r.size() + 1;
        *this = (rev().pre(need) * r.rev().inv(need)).pre(need).rev();
        return *this;
    }
    constexpr FPS &operator%=(const FPS &r) {
        assert(!r.empty());
        assert(r.back() != 0);
        this->normalize();
        FPS q = (*this) / r;
        return *this -= q * r;
    }
    constexpr FPS &operator<<=(int x) {
        FPS res(x, 0);
        res.insert(res.end(), begin(*this), end(*this));
        return *this = res;
    }
    constexpr FPS &operator>>=(int x) {
        FPS res;
        res.insert(res.end(), begin(*this) + x, end(*this));
        return *this = res;
    }

    // advanced operation
    // df/dx
    constexpr FPS diff() const {
        int n = (int)this->size();
        if (n <= 0)
            return FPS();
        FPS res(n - 1);
        for (int i = 1; i < n; ++i)
            res[i - 1] = (*this)[i] * i;
        return res;
    }

    // \int f dx
    constexpr FPS integral() const {
        int n = (int)this->size();
        FPS res(n + 1, 0);
        for (int i = 0; i < n; ++i)
            res[i + 1] = (*this)[i] / (i + 1);
        return res;
    }

    // inv(f), f[0] must not be 0
    constexpr FPS inv(int deg = -1) const {
        if (count_terms() <= SPARSE_BOARDER)
            return inv_sparse(deg);
        if constexpr (std::is_same_v<mint, Fp<998244353>>)
            return inv_ntt_friendly(deg);
        assert(this->size() >= 1 && (*this)[0] != 0);
        if (deg < 0)
            deg = (int)this->size();
        FPS res({mint(1) / (*this)[0]});
        for (int d = 1; d < deg; d <<= 1) {
            res = (res + res - res * res * pre(d << 1)).pre(d << 1);
        }
        res.resize(deg);
        return res;
    }
    constexpr FPS inv_ntt_friendly(int deg = -1) const {
        assert(this->size() >= 1 && (*this)[0] != 0);
        if (deg < 0)
            deg = (int)this->size();
        FPS res(deg);
        res[0] = mint(1) / (*this)[0];
        for (int d = 1; d < deg; d <<= 1) {
            FPS g(d * 2), h(d * 2);
            mint iv = mint(d * 2).inv();
            for (int i = 0; i < min((int)this->size(), d * 2); i++)
                g[i] = (*this)[i];
            for (int i = 0; i < d; i++)
                h[i] = res[i];
            ntt_trans(g), ntt_trans(h);
            for (int i = 0; i < d * 2; i++)
                g[i] *= h[i];
            ntt_trans_inv(g);
            for (int i = 0; i < d; i++)
                g[i] = 0;
            ntt_trans(g);
            for (int i = 0; i < d * 2; i++)
                g[i] *= h[i];
            ntt_trans_inv(g);
            for (int i = d; i < min(deg, d * 2); i++)
                res[i] = -g[i];
        }
        return res.pre(deg);
    }
    constexpr FPS inv_sparse(int deg = -1) const {
        assert(this->size() >= 1 && (*this)[0] != 0);
        if (deg < 0)
            deg = (int)this->size();
        vector<pair<int, mint>> dat;
        for (int i = 1; i < (int)this->size(); i++)
            if ((*this)[i] != mint(0)) {
                dat.emplace_back(i, (*this)[i]);
            }
        vector<mint> res(deg);
        res[0] = (*this)[0].inv();
        for (int i = 1; i < deg; i++) {
            mint r = 0;
            for (auto &&[k, val] : dat) {
                if (k > i)
                    break;
                r -= val * res[i - k];
            }
            res[i] = r * res[0];
        }
        return res;
    }

    // log(f) = \int f'/f dx, f[0] must be 1
    constexpr FPS log(int deg = -1) const {
        assert(this->size() >= 1 && (*this)[0] == 1);
        if (count_terms() <= SPARSE_BOARDER)
            return log_sparse(deg);
        if (deg < 0)
            deg = (int)this->size();
        return ((diff() * inv(deg)).pre(deg - 1)).integral();
    }
    constexpr FPS log_sparse(int deg = -1) const {
        assert(this->size() >= 1 && (*this)[0] == 1);
        if (deg < 0)
            deg = (int)this->size();
        vector<pair<int, mint>> dat;
        for (int i = 1; i < (int)this->size(); i++)
            if ((*this)[i] != mint(0)) {
                dat.emplace_back(i, (*this)[i]);
            }
        BiCoef<mint> bc(deg);
        vector<mint> res(deg), tmp(deg);
        for (int i = 0; i < deg - 1; i++) {
            mint r = mint(i + 1) * (*this)[i + 1];
            for (auto &&[k, val] : dat) {
                if (k > i)
                    break;
                r -= val * tmp[i - k];
            }
            tmp[i] = r;
            res[i + 1] = r * bc.inv(i + 1);
        }
        return res;
    }

    // exp(f), f[0] must be 0
    constexpr FPS exp(int deg = -1) const {
        if ((int)this->size() == 0)
            return {mint(1)};
        if (count_terms() <= SPARSE_BOARDER)
            return exp_sparse(deg);
        if constexpr (std::is_same_v<mint, Fp<998244353>>)
            return exp_ntt_friendly(deg);
        assert((*this)[0] == 0);
        if (deg < 0)
            deg = (int)this->size();
        FPS res(1, 1);
        for (int d = 1; d < deg; d <<= 1) {
            res = res * (pre(d << 1) - res.log(d << 1) + 1).pre(d << 1);
        }
        res.resize(deg);
        return res;
    }
    constexpr FPS exp_ntt_friendly(int deg = -1) const {
        if ((int)this->size() == 0)
            return {mint(1)};
        assert((*this)[0] == 0);
        if (deg < 0)
            deg = (int)this->size();

        FPS fiv;
        fiv.reserve(deg + 1);
        fiv.emplace_back(mint(0));
        fiv.emplace_back(mint(1));

        auto inplace_integral = [&](FPS &F) -> void {
            const int n = (int)F.size();
            auto mod = mint::get_mod();
            while ((int)fiv.size() <= n) {
                int i = fiv.size();
                fiv.emplace_back((-fiv[mod % i]) * (mod / i));
            }
            F.insert(begin(F), mint(0));
            for (int i = 1; i <= n; i++)
                F[i] *= fiv[i];
        };

        auto inplace_diff = [](FPS &F) -> void {
            if (F.empty())
                return;
            F.erase(begin(F));
            mint coef = 1;
            for (int i = 0; i < (int)F.size(); i++) {
                F[i] *= coef;
                coef++;
            }
        };

        FPS b{1, (1 < (int)this->size() ? (*this)[1] : 0)}, c{1}, z1, z2{1, 1};
        for (int m = 2; m < deg; m <<= 1) {
            auto y = b;
            y.resize(m * 2);
            ntt_trans(y);
            z1 = z2;
            FPS z(m);
            for (int i = 0; i < m; i++)
                z[i] = y[i] * z1[i];
            ntt_trans_inv(z);
            fill(begin(z), begin(z) + m / 2, mint(0));
            ntt_trans(z);
            for (int i = 0; i < m; i++)
                z[i] *= -z1[i];
            ntt_trans_inv(z);
            c.insert(end(c), begin(z) + m / 2, end(z));
            z2 = c;
            z2.resize(m * 2);
            ntt_trans(z2);
            FPS x(begin(*this), begin(*this) + min((int)this->size(), m));
            inplace_diff(x);
            x.emplace_back(mint(0));
            ntt_trans(x);
            for (int i = 0; i < m; i++)
                x[i] *= y[i];
            ntt_trans_inv(x);
            x -= b.diff();
            x.resize(m * 2);
            for (int i = 0; i < m - 1; i++)
                x[m + i] = x[i], x[i] = mint(0);
            ntt_trans(x);
            for (int i = 0; i < m * 2; i++)
                x[i] *= z2[i];
            ntt_trans_inv(x);
            x.pop_back();
            inplace_integral(x);
            for (int i = m; i < min((int)this->size(), m * 2); i++)
                x[i] += (*this)[i];
            fill(begin(x), begin(x) + m, mint(0));
            ntt_trans(x);
            for (int i = 0; i < m * 2; i++)
                x[i] *= y[i];
            ntt_trans_inv(x);
            b.insert(end(b), begin(x) + m, end(x));
        }
        return FPS(begin(b), begin(b) + deg);
    }
    constexpr FPS exp_sparse(int deg = -1) const {
        if ((int)this->size() == 0)
            return {mint(1)};
        assert((*this)[0] == 0);
        if (deg < 0)
            deg = (int)this->size();
        vector<pair<int, mint>> dat;
        for (int i = 1; i < (int)this->size(); i++)
            if ((*this)[i] != mint(0)) {
                dat.emplace_back(i - 1, (*this)[i] * i);
            }
        BiCoef<mint> bc(deg);
        vector<mint> res(deg);
        res[0] = 1;
        for (int i = 1; i < deg; i++) {
            mint r = 0;
            for (auto &&[k, val] : dat) {
                if (k > i - 1)
                    break;
                r += val * res[i - k - 1];
            }
            res[i] = r * bc.inv(i);
        }
        return res;
    }

    // pow(f) = exp(e * log f)
    constexpr FPS pow(long long e, int deg = -1) const {
        if (count_terms() <= SPARSE_BOARDER)
            return pow_sparse(e, deg);
        assert(e >= 0);
        if (deg < 0)
            deg = (int)this->size();
        if (deg == 0)
            return FPS();
        if (e == 0) {
            FPS res(deg, 0);
            res[0] = 1;
            return res;
        }
        long long ord = 0;
        while (ord < (int)this->size() && (*this)[ord] == 0)
            ord++;
        if (ord == (int)this->size() || ord > (deg - 1) / e)
            return FPS(deg, 0);
        mint k = (*this)[ord];
        FPS res = ((((*this) >> ord) / k).log(deg) * e).exp(deg) * mint(k).pow(e) << (e * ord);
        res.resize(deg);
        return res;
    }
    constexpr FPS pow_sparse(long long e, int deg = -1) const {
        assert(e >= 0);
        if (deg < 0)
            deg = (int)this->size();
        if (deg == 0)
            return FPS();
        if (e == 0) {
            FPS res(deg, 0);
            res[0] = 1;
            return res;
        }
        long long ord = 0;
        while (ord < (int)this->size() && (*this)[ord] == 0)
            ord++;
        if (ord == (int)this->size() || ord > (deg - 1) / e)
            return FPS(deg, 0);
        if ((*this)[0] == 1)
            return pow_sparse_constant1(e, deg);
        auto f = (*this);
        rotate(f.begin(), f.begin() + ord, f.end());
        mint con = f[0], icon = f[0].inv();
        for (int i = 0; i < deg; i++)
            f[i] *= icon;
        auto res = f.pow_sparse_constant1(e, deg);
        int ord2 = e * ord;
        rotate(res.begin(), res.begin() + (deg - ord2), res.end());
        fill(res.begin(), res.begin() + ord2, mint(0));
        mint pw = con.pow(e);
        for (int i = ord2; i < deg; i++)
            res[i] *= pw;
        return res;
    }
    constexpr FPS pow_sparse_constant1(mint e, int deg = -1) const {
        assert((int)this->size() > 0 && (*this)[0] == 1);
        if (deg < 0)
            deg = (int)this->size();
        vector<pair<int, mint>> dat;
        for (int i = 1; i < (int)this->size(); i++)
            if ((*this)[i] != mint(0)) {
                dat.emplace_back(i, (*this)[i]);
            }
        BiCoef<mint> bc(deg);
        vector<mint> res(deg);
        res[0] = 1;
        for (int i = 0; i < deg - 1; i++) {
            mint &r = res[i + 1];
            for (auto &&[k, val] : dat) {
                if (k > i + 1)
                    break;
                mint t = val * res[i - k + 1];
                r += t * (mint(k) * e - mint(i - k + 1));
            }
            r *= bc.inv(i + 1);
        }
        return res;
    }

    // friend operators
    friend constexpr FPS diff(const FPS &f) { return f.diff(); }
    friend constexpr FPS integral(const FPS &f) { return f.integral(); }
    friend constexpr FPS inv(const FPS &f, int deg = -1) { return f.inv(deg); }
    friend constexpr FPS log(const FPS &f, int deg = -1) { return f.log(deg); }
    friend constexpr FPS exp(const FPS &f, int deg = -1) { return f.exp(deg); }
    friend constexpr FPS pow(const FPS &f, long long e, int deg = -1) { return f.pow(e, deg); }
};

// composition of FPS, calc g(f(x)), O(N (log N)^2)
template <class mint>
FPS<mint> composition(FPS<mint> g, FPS<mint> f, int deg = -1) {
    auto rec = [&](auto &&rec, FPS<mint> Q, int n, int h, int k) -> FPS<mint> {
        if (n == 0) {
            FPS<mint> T{begin(Q), begin(Q) + k};
            T.emplace_back(mint(1));
            FPS<mint> u = g * T.rev().inv().rev();
            FPS<mint> P(h * k);
            for (int i = 0; i < (int)g.size(); i++)
                P[k - i - 1] = u[i + k];
            return P;
        }
        FPS<mint> nQ(h * k * 4), nR(h * k * 2);
        for (int i = 0; i < k; i++) {
            copy(begin(Q) + i * h, begin(Q) + i * h + n + 1, begin(nQ) + i * h * 2);
        }
        nQ[h * k * 2] += 1;
        ntt_trans(nQ);
        for (int i = 0; i < h * k * 4; i += 2)
            swap(nQ[i], nQ[i + 1]);
        for (int i = 0; i < h * k * 2; i++)
            nR[i] = nQ[i * 2] * nQ[i * 2 + 1];
        ntt_trans_inv(nR);
        nR[0] -= 1;
        Q.assign(h * k, 0);
        for (int i = 0; i < k * 2; i++)
            for (int j = 0; j <= n / 2; j++) {
                Q[i * h / 2 + j] = nR[i * h + j];
            }
        auto P = rec(rec, Q, n / 2, h / 2, k * 2);
        FPS<mint> nP(h * k * 4);
        for (int i = 0; i < k * 2; i++)
            for (int j = 0; j <= n / 2; j++) {
                nP[i * h * 2 + j * 2 + n % 2] = P[i * h / 2 + j];
            }
        ntt_trans(nP);
        for (int i = 1; i < h * k * 4; i <<= 1)
            reverse(begin(nQ) + i, begin(nQ) + i * 2);
        for (int i = 0; i < h * k * 4; i++)
            nP[i] *= nQ[i];
        ntt_trans_inv(nP);
        P.assign(h * k, 0);
        for (int i = 0; i < k; i++) {
            copy(begin(nP) + i * h * 2, begin(nP) + i * h * 2 + n + 1, begin(P) + i * h);
        }
        return P;
    };
    if (deg == -1)
        deg = max((int)f.size(), (int)g.size());
    f.resize(deg), g.resize(deg);
    int n = (int)f.size() - 1, h = 1, k = 1;
    while (h < n + 1)
        h *= 2;
    FPS<mint> Q(h * k);
    for (int i = 0; i <= n; i++)
        Q[i] = -f[i];
    FPS<mint> P = rec(rec, Q, n, h, k);
    return P.pre(n + 1).rev();
}

#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    using mint = Fp<998244353>;
    vector<mint> a(n), b(n), c(n);
    rep(i, n) cin >> a[i];
    rep(i, n) cin >> b[i];
    rep(i, n) cin >> c[i];
    rep(i, n) b[i] *= a[1].pow(m);
    auto d = composition<mint>(c, b);
    rep(i, n) cout << d[i] << " ";
    cout << endl;
    return 0;
}