#include <iostream>
#include <type_traits>

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 2 "poly.hpp"

#line 2 "poly_basic.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 6 "semi_relaxed_conv.hpp"
#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, 0);
            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, 0);
    return a;
}
#line 10 "poly_basic.hpp"

template <typename Tp>
inline int degree(const std::vector<Tp> &a) {
    int n = (int)a.size() - 1;
    while (n >= 0 && a[n] == 0) --n;
    return n;
}

template <typename Tp>
inline void shrink(std::vector<Tp> &a) {
    a.resize(degree(a) + 1);
}

template <typename Tp>
inline std::vector<Tp> taylor_shift(std::vector<Tp> a, Tp c) {
    const int n = a.size();
    auto &&bin  = Binomial<Tp>::get(n);
    for (int i = 0; i < n; ++i) a[i] *= bin.factorial(i);
    Tp cc = 1;
    std::vector<Tp> b(n);
    for (int i = 0; i < n; ++i) {
        b[i] = cc * bin.inv_factorial(i);
        cc *= c;
    }
    std::reverse(a.begin(), a.end());
    auto ab = convolution(a, b);
    ab.resize(n);
    std::reverse(ab.begin(), ab.end());
    for (int i = 0; i < n; ++i) ab[i] *= bin.inv_factorial(i);
    return ab;
}

// returns (quotient, remainder)
// O(deg(Q)deg(B))
template <typename Tp>
inline std::pair<std::vector<Tp>, std::vector<Tp>> euclidean_div_naive(const std::vector<Tp> &A,
                                                                       const std::vector<Tp> &B) {
    const int degA = degree(A);
    const int degB = degree(B);
    assert(degB >= 0);
    const int degQ = degA - degB;
    if (degQ < 0) return {std::vector<Tp>{Tp(0)}, A};
    std::vector<Tp> Q(degQ + 1), R = A;
    const auto inv = B[degB].inv();
    for (int i = degQ, n = degA; i >= 0; --i)
        if ((Q[i] = R[n--] * inv) != 0)
            for (int j = 0; j <= degB; ++j) R[i + j] -= Q[i] * B[j];
    R.resize(degB);
    return {Q, R};
}

// O(min(deg(Q)^2,deg(Q)deg(B)))
template <typename Tp>
inline std::vector<Tp> euclidean_div_quotient_naive(const std::vector<Tp> &A,
                                                    const std::vector<Tp> &B) {
    const int degA = degree(A);
    const int degB = degree(B);
    assert(degB >= 0);
    const int degQ = degA - degB;
    if (degQ < 0) return {Tp(0)};
    const auto inv = B[degB].inv();
    std::vector<Tp> Q(degQ + 1);
    for (int i = 0; i <= degQ; ++i) {
        for (int j = 1; j <= std::min(i, degB); ++j) Q[degQ - i] += B[degB - j] * Q[degQ - i + j];
        Q[degQ - i] = (A[degA - i] - Q[degQ - i]) * inv;
    }
    return Q;
}

// returns (quotient, remainder)
template <typename Tp>
inline std::pair<std::vector<Tp>, std::vector<Tp>> euclidean_div(const std::vector<Tp> &A,
                                                                 const std::vector<Tp> &B) {
    const int degA = degree(A);
    const int degB = degree(B);
    assert(degB >= 0);
    // A = Q*B + R => A/B = Q + R/B in R((x^(-1)))
    const int degQ = degA - degB;
    if (degQ < 0) return {std::vector<Tp>{Tp(0)}, A};
    if (degQ < 60 || degB < 60) return euclidean_div_naive(A, B);

    auto Q = div(std::vector(A.rend() - (degA + 1), A.rend()),
                 std::vector(B.rend() - (degB + 1), B.rend()), degQ + 1);
    std::reverse(Q.begin(), Q.end());

    // returns a mod (x^n-1)
    auto make_cyclic = [](const std::vector<Tp> &a, int n) {
        assert((n & (n - 1)) == 0);
        std::vector<Tp> b(n);
        for (int i = 0; i < (int)a.size(); ++i) b[i & (n - 1)] += a[i];
        return b;
    };

    const int len      = fft_len(std::max(degB, 1));
    const auto cyclicA = make_cyclic(A, len);
    auto cyclicB       = make_cyclic(B, len);
    auto cyclicQ       = make_cyclic(Q, len);

    fft(cyclicQ);
    fft(cyclicB);
    for (int i = 0; i < len; ++i) cyclicQ[i] *= cyclicB[i];
    inv_fft(cyclicQ);

    // R = A - QB mod (x^n-1) (n >= degB)
    std::vector<Tp> R(degB);
    for (int i = 0; i < degB; ++i) R[i] = cyclicA[i] - cyclicQ[i];
    return {Q, R};
}

template <typename Tp>
inline std::vector<Tp> euclidean_div_quotient(const std::vector<Tp> &A, const std::vector<Tp> &B) {
    const int degA = degree(A);
    const int degB = degree(B);
    assert(degB >= 0);
    // A = Q*B + R => A/B = Q + R/B in R((x^(-1)))
    const int degQ = degA - degB;
    if (degQ < 0) return {Tp(0)};
    if (std::min(degQ, degB) < 60) return euclidean_div_quotient_naive(A, B);

    auto Q = div(std::vector(A.rend() - (degA + 1), A.rend()),
                 std::vector(B.rend() - (degB + 1), B.rend()), degQ + 1);
    std::reverse(Q.begin(), Q.end());
    return Q;
}
#line 5 "poly.hpp"
#include <array>
#line 8 "poly.hpp"
#include <tuple>
#line 11 "poly.hpp"

template <typename Tp>
class Poly : public std::vector<Tp> {
    using Base = std::vector<Tp>;

public:
    using Base::Base;

    static Poly from_vector(const std::vector<Tp> &V) { return Poly(V.begin(), V.end()); }

    int deg() const { return degree(*this); }

    int ord() const { return order(*this); }

    Poly rev() const {
        const int d = deg();
        Poly res(d + 1);
        for (int i = d; i >= 0; --i) res[i] = Base::operator[](d - i);
        return res;
    }

    Poly slice(int L, int R) const {
        Poly res(R - L);
        for (int i = L; i < std::min(R, (int)Base::size()); ++i) res[i - L] = Base::operator[](i);
        return res;
    }

    Poly trunc(int D) const {
        Poly res(D);
        for (int i = 0; i < std::min(D, (int)Base::size()); ++i) res[i] = Base::operator[](i);
        return res;
    }

    Poly &shrink() {
        Base::resize(deg() + 1);
        return *this;
    }

    Tp lc() const {
        const int d = deg();
        return d == -1 ? Tp() : Base::operator[](d);
    }

    Poly operator-() const {
        const int d = deg();
        Poly res(d + 1);
        for (int i = 0; i <= d; ++i) res[i] = -Base::operator[](i);
        res.shrink();
        return res;
    }

    std::pair<Poly, Poly> divmod(const Poly &R) const {
        const auto [q, r] = euclidean_div(*this, R);
        return std::make_pair(from_vector(q), from_vector(r));
    }
    Poly &operator+=(const Poly &R) {
        if (Base::size() < R.size()) Base::resize(R.size());
        for (int i = 0; i < (int)R.size(); ++i) Base::operator[](i) += R[i];
        return shrink();
    }
    Poly &operator-=(const Poly &R) {
        if (Base::size() < R.size()) Base::resize(R.size());
        for (int i = 0; i < (int)R.size(); ++i) Base::operator[](i) -= R[i];
        return shrink();
    }
    Poly &operator*=(const Poly &R) {
        Base::operator=(convolution(*this, R));
        return shrink();
    }
    Poly &operator/=(const Poly &R) {
        Base::operator=(euclidean_div_quotient(*this, R));
        return shrink();
    }
    Poly &operator%=(const Poly &R) {
        Base::operator=(divmod(R).second);
        return shrink();
    }
    Poly &operator<<=(int D) {
        if (D > 0) {
            Base::insert(Base::begin(), D, Tp());
        } else if (D < 0) {
            if (-D < (int)Base::size()) {
                Base::erase(Base::begin(), Base::begin() + (-D));
            } else {
                Base::clear();
            }
        }
        return shrink();
    }
    Poly &operator>>=(int D) { return operator<<=(-D); }

    friend Poly operator+(const Poly &L, const Poly &R) { return Poly(L) += R; }
    friend Poly operator-(const Poly &L, const Poly &R) { return Poly(L) -= R; }
    friend Poly operator*(const Poly &L, const Poly &R) { return Poly(L) *= R; }
    friend Poly operator/(const Poly &L, const Poly &R) { return Poly(L) /= R; }
    friend Poly operator%(const Poly &L, const Poly &R) { return Poly(L) %= R; }
    friend Poly operator<<(const Poly &L, int D) { return Poly(L) <<= D; }
    friend Poly operator>>(const Poly &L, int D) { return Poly(L) >>= D; }

    friend std::ostream &operator<<(std::ostream &L, const Poly &R) {
        L << '[';
        const int d = R.deg();
        if (d < 0) {
            L << '0';
        } else {
            for (int i = 0; i <= d; ++i) {
                L << R[i];
                if (i == 1) L << "*x";
                if (i > 1) L << "*x^" << i;
                if (i != d) L << " + ";
            }
        }
        return L << ']';
    }
};

// 2x2 matrix for Euclidean algorithm
template <typename Tp>
class GCDMatrix : public std::array<std::array<Tp, 2>, 2> {
public:
    GCDMatrix(const Tp &x00, const Tp &x01, const Tp &x10, const Tp &x11)
        : std::array<std::array<Tp, 2>, 2>{std::array{x00, x01}, std::array{x10, x11}} {}

    GCDMatrix operator*(const GCDMatrix &R) const {
        return {(*this)[0][0] * R[0][0] + (*this)[0][1] * R[1][0],
                (*this)[0][0] * R[0][1] + (*this)[0][1] * R[1][1],
                (*this)[1][0] * R[0][0] + (*this)[1][1] * R[1][0],
                (*this)[1][0] * R[0][1] + (*this)[1][1] * R[1][1]};
    }

    std::array<Tp, 2> operator*(const std::array<Tp, 2> &R) const {
        return {(*this)[0][0] * R[0] + (*this)[0][1] * R[1],
                (*this)[1][0] * R[0] + (*this)[1][1] * R[1]};
    }

    Tp det() const { return (*this)[0][0] * (*this)[1][1] - (*this)[0][1] * (*this)[1][0]; }
    GCDMatrix adj() const { return {(*this)[1][1], -(*this)[0][1], -(*this)[1][0], (*this)[0][0]}; }
};

// returns M s.t. deg(M) <= d and deg(M21*A+M22*B) < max(deg(A),deg(B))-d
//                det(M) in {-1,1}
// see:
// [1]: Daniel J. Bernstein. Fast multiplication and its applications.
template <typename Tp>
inline GCDMatrix<Poly<Tp>> hgcd(const Poly<Tp> &A, const Poly<Tp> &B, int d) {
    using Mat = GCDMatrix<Poly<Tp>>;
    assert(!(A.deg() < 0 && B.deg() < 0));
    if (A.deg() < B.deg()) return hgcd(B, A, d) * Mat({}, {Tp(1)}, {Tp(1)}, {});
    if (A.deg() < d) return hgcd(A, B, A.deg());
    if (B.deg() < 0 || B.deg() < A.deg() - d) return Mat({Tp(1)}, {}, {}, {Tp(1)});
    if (int dd = A.deg() - d * 2; dd > 0) return hgcd(A >> dd, B >> dd, d);
    if (d == 0) return Mat({}, {Tp(1)}, {Tp(1)}, -(A / B));
    const auto M = hgcd(A, B, d / 2);
    const auto D = M[1][0] * A + M[1][1] * B;
    if (D.deg() < A.deg() - d) return M;
    const auto C      = M[0][0] * A + M[0][1] * B;
    const auto [Q, R] = C.divmod(D);
    return hgcd(D, R, D.deg() - (A.deg() - d)) * Mat({}, {Tp(1)}, {Tp(1)}, -Q) * M;
}

template <typename Tp>
inline std::tuple<Poly<Tp>, Poly<Tp>, Poly<Tp>> xgcd(const Poly<Tp> &A, const Poly<Tp> &B) {
    const auto M = hgcd(A, B, std::max(A.deg(), B.deg()));
    return std::make_tuple(M[0][0], M[0][1], M[0][0] * A + M[0][1] * B);
}

template <typename Tp>
inline std::pair<Poly<Tp>, Poly<Tp>> inv_gcd(const Poly<Tp> &A, const Poly<Tp> &B) {
    const auto M = hgcd(A, B, std::max(A.deg(), B.deg()));
    return std::make_pair(M[0][0], M[0][0] * A + M[0][1] * B);
}

// returns P,Q s.t. [x^([-k,-1])]P/Q=[x^([-k,-1])]A/B
// where P,Q in F[x], deg(Q) is minimized
// requires deg(A)<deg(B)
template <typename Tp>
inline std::pair<Poly<Tp>, Poly<Tp>> rational_function_approximation(const Poly<Tp> &A,
                                                                     const Poly<Tp> &B, int k) {
    auto M            = hgcd(B, A, k / 2);
    const auto [C, D] = M * std::array{B, A};
    if (D.deg() >= 0 && D.deg() - C.deg() >= -(k - (B.deg() - C.deg()) * 2))
        M = GCDMatrix<Poly<Tp>>({}, {Tp(1)}, {Tp(1)}, -(C / D)) * M;
    return std::make_pair(M.adj()[1][0], M.adj()[0][0]);
}

// returns [x^([-k,-1])]A/B
// requires deg(A)<deg(B)
template <typename Tp>
inline std::vector<Tp> rational_function_to_series(const Poly<Tp> &A, const Poly<Tp> &B, int k) {
    return (((A << k) / B).rev() << (B.deg() - A.deg() - 1)).slice(0, k);
}

using mint = ModInt<998244353>;
using namespace std;

#define len(a) int(a.size())
#define all(a) begin(a), end(a)

namespace lol {

#include <algorithm>
#include <bit>
// ============
#include <algorithm>
// ============
#include <array>
#include <vector>
// ============

#include <cassert>
#include <iostream>
#include <type_traits>
// ============

#include <utility>

constexpr bool is_prime(unsigned n) {
    if (n == 0 || n == 1) {
        return false;
    }
    for (unsigned i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

constexpr unsigned mod_pow(unsigned x, unsigned y, unsigned mod) {
    unsigned ret = 1, self = x;
    while (y != 0) {
        if (y & 1) {
            ret = (unsigned)((unsigned long long)ret * self % mod);
        }
        self = (unsigned)((unsigned long long)self * self % mod);
        y /= 2;
    }
    return ret;
}

template <unsigned mod>
constexpr unsigned primitive_root() {
    static_assert(is_prime(mod), "`mod` must be a prime number.");
    if (mod == 2) {
        return 1;
    }

    unsigned primes[32] = {};
    int it = 0;
    {
        unsigned m = mod - 1;
        for (unsigned i = 2; i * i <= m; ++i) {
            if (m % i == 0) {
                primes[it++] = i;
                while (m % i == 0) {
                    m /= i;
                }
            }
        }
        if (m != 1) {
            primes[it++] = m;
        }
    }
    for (unsigned i = 2; i < mod; ++i) {
        bool ok = true;
        for (int j = 0; j < it; ++j) {
            if (mod_pow(i, (mod - 1) / primes[j], mod) == 1) {
                ok = false;
                break;
            }
        }
        if (ok) return i;
    }
    return 0;
}

// y >= 1
template <typename T>
constexpr T safe_mod(T x, T y) {
    x %= y;
    if (x < 0) {
        x += y;
    }
    return x;
}

// y != 0
template <typename T>
constexpr T floor_div(T x, T y) {
    if (y < 0) {
        x *= -1;
        y *= -1;
    }
    if (x >= 0) {
        return x / y;
    } else {
        return -((-x + y - 1) / y);
    }
}

// y != 0
template <typename T>
constexpr T ceil_div(T x, T y) {
    if (y < 0) {
        x *= -1;
        y *= -1;
    }
    if (x >= 0) {
        return (x + y - 1) / y;
    } else {
        return -(-x / y);
    }
}

// b >= 1
// returns (g, x) s.t. g = gcd(a, b), a * x = g (mod b), 0 <= x < b / g
// from ACL
template <typename T>
std::pair<T, T> extgcd(T a, T b) {
    a = safe_mod(a, b);
    T s = b, t = a, m0 = 0, m1 = 1;
    while (t) {
        T u = s / t;
        s -= t * u;
        m0 -= m1 * u;
        std::swap(s, t);
        std::swap(m0, m1);
    }
    if (m0 < 0) {
        m0 += b / s;
    }
    return std::pair<T, T>(s, m0);
}

// b >= 1
// returns (g, x, y) s.t. g = gcd(a, b), a * x + b * y = g, 0 <= x < b / g, |y| < max(2, |a| / g)
template <typename T>
std::tuple<T, T, T> extgcd2(T a, T b) {
    T _a = safe_mod(a, b);
    T quot = (a - _a) / b;
    T x00 = 0, x01 = 1, y0 = b;
    T x10 = 1, x11 = -quot, y1 = _a;
    while (y1) {
        T u = y0 / y1;
        x00 -= u * x10;
        x01 -= u * x11;
        y0 -= u * y1;
        std::swap(x00, x10);
        std::swap(x01, x11);
        std::swap(y0, y1);
    }
    if (x00 < 0) {
        x00 += b / y0;
        x01 -= a / y0;
    }
    return std::tuple<T, T, T>(y0, x00, x01);
}

// gcd(x, m) == 1
template <typename T>
T inv_mod(T x, T m) {
    return extgcd(x, m).second;
}
// ============

template <unsigned mod>
struct ModInt {
    static_assert(mod != 0, "`mod` must not be equal to 0.");
    static_assert(mod < (1u << 31),
                  "`mod` must be less than (1u << 31) = 2147483648.");

    unsigned val;

    static constexpr unsigned get_mod() { return mod; }

    constexpr ModInt() : val(0) {}
    template <typename T, std::enable_if_t<std::is_signed_v<T>> * = nullptr>
    constexpr ModInt(T x)
        : val((unsigned)((long long)x % (long long)mod + (x < 0 ? mod : 0))) {}
    template <typename T, std::enable_if_t<std::is_unsigned_v<T>> * = nullptr>
    constexpr ModInt(T x) : val((unsigned)(x % mod)) {}

    static constexpr ModInt raw(unsigned x) {
        ModInt<mod> ret;
        ret.val = x;
        return ret;
    }

    constexpr unsigned get_val() const { return val; }

    constexpr ModInt operator+() const { return *this; }
    constexpr ModInt operator-() const { return ModInt<mod>(0u) - *this; }

    constexpr ModInt &operator+=(const ModInt &rhs) {
        val += rhs.val;
        if (val >= mod) val -= mod;
        return *this;
    }
    constexpr ModInt &operator-=(const ModInt &rhs) {
        val -= rhs.val;
        if (val >= mod) val += mod;
        return *this;
    }
    constexpr ModInt &operator*=(const ModInt &rhs) {
        val = (unsigned long long)val * rhs.val % mod;
        return *this;
    }
    constexpr ModInt &operator/=(const ModInt &rhs) {
        val = (unsigned long long)val * rhs.inv().val % mod;
        return *this;
    }

    friend constexpr ModInt operator+(const ModInt &lhs, const ModInt &rhs) {
        return ModInt<mod>(lhs) += rhs;
    }
    friend constexpr ModInt operator-(const ModInt &lhs, const ModInt &rhs) {
        return ModInt<mod>(lhs) -= rhs;
    }
    friend constexpr ModInt operator*(const ModInt &lhs, const ModInt &rhs) {
        return ModInt<mod>(lhs) *= rhs;
    }
    friend constexpr ModInt operator/(const ModInt &lhs, const ModInt &rhs) {
        return ModInt<mod>(lhs) /= rhs;
    }

    constexpr ModInt pow(unsigned long long x) const {
        ModInt<mod> ret = ModInt<mod>::raw(1);
        ModInt<mod> self = *this;
        while (x != 0) {
            if (x & 1) ret *= self;
            self *= self;
            x >>= 1;
        }
        return ret;
    }
    constexpr ModInt inv() const {
        static_assert(is_prime(mod), "`mod` must be a prime number.");
        assert(val != 0);
        return this->pow(mod - 2);
    }

    friend std::istream &operator>>(std::istream &is, ModInt<mod> &x) {
        long long val;
        is >> val;
        x.val = val % mod + (val < 0 ? mod : 0);
        return is;
    }

    friend std::ostream &operator<<(std::ostream &os, const ModInt<mod> &x) {
        os << x.val;
        return os;
    }

    friend bool operator==(const ModInt &lhs, const ModInt &rhs) {
        return lhs.val == rhs.val;
    }

    friend bool operator!=(const ModInt &lhs, const ModInt &rhs) {
        return lhs.val != rhs.val;
    }
};

template <unsigned mod>
void debug(ModInt<mod> x) {
    std::cerr << x.val;
}
// ============

constexpr int ctz_constexpr(unsigned n) {
    int x = 0;
    while (!(n & (1u << x))) {
        ++x;
    }
    return x;
}

template <unsigned MOD>
struct FFTRoot {
    static constexpr unsigned R = ctz_constexpr(MOD - 1);
    std::array<ModInt<MOD>, R + 1> root, iroot;
    std::array<ModInt<MOD>, R> rate2, irate2;
    std::array<ModInt<MOD>, R - 1> rate3, irate3;
    std::array<ModInt<MOD>, R + 1> inv2;

    constexpr FFTRoot() : root{}, iroot{}, rate2{}, irate2{}, rate3{}, irate3{}, inv2{} {
        unsigned pr = primitive_root<MOD>();
        root[R] = ModInt<MOD>(pr).pow(MOD >> R);
        iroot[R] = root[R].inv();
        for (int i = R - 1; i >= 0; --i) {
            root[i] = root[i + 1] * root[i + 1];
            iroot[i] = iroot[i + 1] * iroot[i + 1];
        }
        ModInt<MOD> prod(1), iprod(1);
        for (int i = 0; i < (int)R - 1; ++i) {
            rate2[i] = prod * root[i + 2];
            irate2[i] = iprod * iroot[i + 2];
            prod *= iroot[i + 2];
            iprod *= root[i + 2];
        }
        prod = ModInt<MOD>(1);
        iprod = ModInt<MOD>(1);
        for (int i = 0; i < (int)R - 2; ++i) {
            rate3[i] = prod * root[i + 3];
            irate3[i] = iprod * iroot[i + 3];
            prod *= iroot[i + 3];
            iprod *= root[i + 3];
        }
        ModInt<MOD> i2 = ModInt<MOD>(2).inv();
        inv2[0] = ModInt<MOD>(1);
        for (int i = 0; i < (int)R; ++i) {
            inv2[i + 1] = inv2[i] * i2;
        }
    }
};

template <typename M>
void fft(M *a, int n) {
    using ull = unsigned long long;
    static_assert(M::get_mod() < (1u << 30));
    static constexpr FFTRoot<M::get_mod()> fftroot;
    static constexpr ull CEIL = 2ULL * M::get_mod() * M::get_mod();
    int l = __builtin_ctz(n);
    int ph = 0;
    while (ph < l) {
        if (ph + 1 == l) {
            int b = 1 << ph;
            M z = M::raw(1);
            for (int i = 0; i < b; ++i) {
                int offset = i << 1;
                M x = a[offset];
                M y = a[offset + 1] * z;
                a[offset] = x + y;
                a[offset + 1] = x - y;
                z *= fftroot.rate2[__builtin_ctz(~i)];
            }
            ++ph;
        } else {
            int bl = 1 << ph;
            int wd = 1 << (l - 2 - ph);
            M zeta = M::raw(1);
            for (int i = 0; i < bl; ++i) {
                int offset = i << (l - ph);
                M zeta2 = zeta * zeta;
                M zeta3 = zeta2 * zeta;
                for (int j = 0; j < wd; ++j) {
                    ull w = a[offset + j].val;
                    ull x = (ull)a[offset + j + wd].val * zeta.val;
                    ull y = (ull)a[offset + j + 2 * wd].val * zeta2.val;
                    ull z = (ull)a[offset + j + 3 * wd].val * zeta3.val;
                    ull ix_m_iz = (CEIL + x - z) % M::get_mod() * fftroot.root[2].val;
                    a[offset + j] = M(w + x + y + z);
                    a[offset + j + wd] = M(CEIL + w - x + y - z);
                    a[offset + j + 2 * wd] = M(CEIL + w - y + ix_m_iz);
                    a[offset + j + 3 * wd] = M(CEIL + w - y - ix_m_iz);
                }
                zeta *= fftroot.rate3[__builtin_ctz(~i)];
            }
            ph += 2;
        }
    }
}

template <typename M>
void ifft(M *a, int n) {
    using ull = unsigned long long;
    static_assert(M::get_mod() < (1u << 30));
    static constexpr FFTRoot<M::get_mod()> fftroot;
    int l = __builtin_ctz(n);
    int ph = l;
    while (ph > 0) {
        if (ph == 1) {
            --ph;
            int wd = 1 << (l - 1);
            for (int i = 0; i < wd; ++i) {
                M x = a[i];
                M y = a[i + wd];
                a[i] = x + y;
                a[i + wd] = x - y;
            }
        } else {
            ph -= 2;
            int bl = 1 << ph;
            int wd = 1 << (l - 2 - ph);
            M zeta = M::raw(1);
            for (int i = 0; i < bl; ++i) {
                int offset = i << (l - ph);
                M zeta2 = zeta * zeta;
                M zeta3 = zeta2 * zeta;
                for (int j = 0; j < wd; ++j) {
                    unsigned w = a[offset + j].val;
                    unsigned x = a[offset + j + wd].val;
                    unsigned y = a[offset + j + 2 * wd].val;
                    unsigned z = a[offset + j + 3 * wd].val;
                    unsigned iy_m_iz = (ull)(M::get_mod() + y - z) * fftroot.root[2].val % M::get_mod();
                    a[offset + j] = M(w + x + y + z);
                    a[offset + j + wd] = M((ull)zeta.val * (2 * M::get_mod() + w - x - iy_m_iz));
                    a[offset + j + 2 * wd] = M((ull)zeta2.val * (2 * M::get_mod() + w + x - y - z));
                    a[offset + j + 3 * wd] = M((ull)zeta3.val * (M::get_mod() + w - x + iy_m_iz));
                }
                zeta *= fftroot.irate3[__builtin_ctz(~i)];
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        a[i] *= fftroot.inv2[l];
    }
}

template <typename M>
void fft(std::vector<M> &a) {
    fft(a.data(), (int)a.size());
}
template <typename M>
void ifft(std::vector<M> &a) {
    ifft(a.data(), (int)a.size());
}

template <typename M>
std::vector<M> convolve_naive(const std::vector<M> &a,
                              const std::vector<M> &b) {
    int n = (int)a.size();
    int m = (int)b.size();
    std::vector<M> c(n + m - 1);
    if (n < m) {
        for (int j = 0; j < m; ++j) {
            for (int i = 0; i < n; ++i) {
                c[i + j] += a[i] * b[j];
            }
        }
    } else {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                c[i + j] += a[i] * b[j];
            }
        }
    }
    return c;
}

template <typename M>
std::vector<M> convolve_fft(std::vector<M> a, std::vector<M> b) {
    int n = (int)a.size() + (int)b.size() - 1;
    int m = 1;
    while (m < n) {
        m <<= 1;
    }
    bool shr = false;
    M last;
    if (n >= 3 && n == m / 2 + 1) {
        shr = true;
        last = a.back() * b.back();
        m /= 2;
        while ((int)a.size() > m) {
            a[(int)a.size() - 1 - m] += a.back();
            a.pop_back();
        }
        while ((int)b.size() > m) {
            b[(int)b.size() - 1 - m] += b.back();
            b.pop_back();
        }
    }
    a.resize(m);
    b.resize(m);
    fft(a);
    fft(b);
    for (int i = 0; i < m; ++i) {
        a[i] *= b[i];
    }
    ifft(a);
    a.resize(n);
    if (shr) {
        a[0] -= last;
        a[n - 1] = last;
    }
    return a;
}

template <typename M>
std::vector<M> convolve(const std::vector<M> &a, const std::vector<M> &b) {
    if (a.empty() || b.empty()) {
        return std::vector<M>(0);
    }
    if (std::min(a.size(), b.size()) <= 60) {
        return convolve_naive(a, b);
    } else {
        return convolve_fft(a, b);
    }
}
// ============
// 10 FFT(n)
template <typename T>
std::vector<T> fps_inv(std::vector<T> f) {
    assert(!f.empty() && f[0] != T(0));
    std::vector<T> g(1, T(1) / f[0]);
    while (g.size() < f.size()) {
        int n = (int)g.size();
        std::vector<T> fft_f(2 * n), fft_g(2 * n);
        std::copy(f.begin(), f.begin() + std::min(2 * n, (int)f.size()),
                  fft_f.begin());
        std::copy(g.begin(), g.end(), fft_g.begin());
        fft(fft_f);
        fft(fft_g);
        for (int i = 0; i < 2 * n; ++i) {
            fft_f[i] *= fft_g[i];
        }
        ifft(fft_f);
        std::fill(fft_f.begin(), fft_f.begin() + n, T(0));
        fft(fft_f);
        for (int i = 0; i < 2 * n; ++i) {
            fft_f[i] *= fft_g[i];
        }
        ifft(fft_f);
        g.resize(2 * n);
        for (int i = n; i < 2 * n; ++i) {
            g[i] = -fft_f[i];
        }
    }
    g.resize(f.size());
    return g;
}
// ============
template <typename M>
void extend_fft(std::vector<M> &a) {
    static constexpr FFTRoot<M::get_mod()> fft_root;
    int n = (int)a.size();
    std::copy(a.begin(), a.begin() + n / 2, a.begin() + n / 2);
    ifft(a.data() + n / 2, n / 2);
    M pw(1);
    M r = fft_root.root[std::bit_width((unsigned)n) - 1];
    for (int i = n / 2; i < n; ++i) {
        a[i] *= pw;
        pw *= r;
    }
    fft(a.data() + n / 2, n / 2);
}
// returns [x^k] f(x) / g(x)
// requires LEN(f) < LEN(g) and g[0] != 0
template <typename T>
T fps_div_at(std::vector<T> f, std::vector<T> g, long long k) {
    static constexpr FFTRoot<T::get_mod()> fft_root;
    static constexpr T INV2 = T(2).inv();
    assert(f.size() < g.size() && g[0] != T(0));
    if (g.size() == 1) {
        return T(0);
    }
    int n = (int)std::bit_ceil(2 * g.size() - 1);
    f.resize(n, T(0));
    g.resize(n, T(0));
    fft(f);
    fft(g);
    while (k >= n) {
        for (int i = 0; i < n; ++i) {
            f[i] *= g[i ^ 1];
        }
        if (k & 1) {
            T p(1);
            for (int i = 0; i < n / 2; ++i) {
                f[i] = (f[2 * i] - f[2 * i + 1]) * INV2 * p;
                p *= fft_root.irate2[__builtin_ctz(~i)];
            }
        } else {
            for (int i = 0; i < n / 2; ++i) {
                f[i] = (f[2 * i] + f[2 * i + 1]) * INV2;
            }
        }
        extend_fft(f);
        for (int i = 0; i < n / 2; ++i) {
            g[i] = g[2 * i] * g[2 * i + 1];
        }
        extend_fft(g);
        k /= 2;
    }
    ifft(f);
    ifft(g);
    std::vector<T> inv_g = fps_inv(g);
    T ans(0);
    for (int i = 0; i <= k; ++i) {
        ans += f[i] * inv_g[k - i];
    }
    return ans;
}

int solve(int d, int64_t k, vector<int> aa, vector<int> rr) {
    using M = ModInt<998244353>;
    vector<M> a(d);
    for (int i = 0; i < d; i++) {
        a[i] = aa[i];
    }
    vector<M> c(d);
    for (int i = 0; i < d; i++) {
        c[i] = rr[i];
    }
    vector<M> den(d + 1);
    den[0] = M(1);
    for (int i = 0; i < d; i++) {
        den[i + 1] = -c[i];
    }
    vector<M> num = convolve(a, den);
    num.resize(d);
    M ans = fps_div_at(num, den, k);
    return ans.val;
}

}

namespace berlekamp_massey {
    template<typename T>
    std::vector<T> find_recurrence(const std::vector<T> &values) {
        if (values.empty())
            return {};

        std::vector<T> add_option{}, recurrence{};
        int add_position = -1;
        T add_value = values[1];
        for (int i = 0; i < int(values.size()); i++) {
            T value = 0;
            for (int j = 0; j < int(recurrence.size()); j++)
                value += values[i - j - 1] * recurrence[j];

            T delta = values[i] - value;
            if (delta == 0)
                continue;

            std::vector<T> new_recurrence;
            if (add_position == -1) {
                new_recurrence.assign(i + 1, 0);
            } else {
                new_recurrence = add_option;
                std::reverse(new_recurrence.begin(), new_recurrence.end());
                new_recurrence.push_back(-1);
                for (int it = 0; it < i - add_position - 1; it++)
                    new_recurrence.push_back(0);
                
                std::reverse(new_recurrence.begin(), new_recurrence.end());
                T coeff = -delta / add_value;
                for (auto &x : new_recurrence)
                    x *= coeff;

                if (new_recurrence.size() < recurrence.size())
                    new_recurrence.resize(recurrence.size());

                for (int i = 0; i < int(recurrence.size()); i++)
                    new_recurrence[i] += recurrence[i];
            }

            if (i - int(recurrence.size()) >= add_position - int(add_option.size()) || add_position == -1) {
                add_option = recurrence;
                add_position = i;
                add_value = delta;
            }
            recurrence = new_recurrence;
        }
        return recurrence;
    }

    template<typename T>
    std::vector<T> multiply(const std::vector<T> &first, const std::vector<T> &second) {
        // can be replaced with fft multiplication
        std::vector<T> prod(max(0, int(first.size() + second.size()) - 1));
        for (int i = 0; i < int(first.size()); i++)
            for (int j = 0; j < int(second.size()); j++)
                prod[i + j] += first[i] * second[j];

        return prod;
    }

    template<typename T>
    std::vector<T> find_remainder(std::vector<T> first, const std::vector<T> &second) {
        // can be replaced with fft division
        if (second.empty())
            return {};

        assert(second.back() != 0);
        while (!first.empty() && first.size() >= second.size()) {
            if (first.back() == 0) {
                first.pop_back();
                continue;
            }
            T coeff = first.back() / second.back();
            for (int i = 0; i < int(second.size()); i++)
                first[int(first.size()) - int(second.size()) + i] -= coeff * second[i];
        }
        return first;
    }

    template<typename T>
    std::vector<T> find_remainder(std::vector<T> recurrence, int64_t k) {
        while (!recurrence.empty() && recurrence.back() == 0)
            recurrence.pop_back();

        std::vector<T> result{1}, value{0, 1};
        for (; k; k >>= 1) {
            if (k & 1)
                result = find_remainder(multiply(result, value), recurrence);

            value = find_remainder(multiply(value, value), recurrence);
        }
        return result;
    }

    template<typename T>
    T find_kth(const std::vector<T> &values, std::vector<T> recurrence, int64_t k) {
        std::reverse(recurrence.begin(), recurrence.end());
        recurrence.push_back(-1);
        std::vector<T> poly = find_remainder(recurrence, k);
        T result = 0;
        for (int i = 0; i < int(poly.size()); i++)
            result += poly[i] * values[i];

        return result;
    }
} // berlekamp_massey

signed main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  int n, m;
  int64_t k;
  cin >> n >> m >> k;
  k--;

  vector g(n, vector<int>(n));
  while (m--) {
    int v, u;
    cin >> v >> u;
    v--, u--;
    g[v][u] = 1;
    g[u][v] = 1;
  }

  vector dp(n, vector<mint>(n));
  for (int j = 1; j < n; j++) {
    if (g[0][j]) {
      dp[0][j] = 1;
    }
  }

  auto get_ans = [&]() {
    mint ans = 0;
    for (int i = 0; i < n - 1; i++) {
        ans += dp[i][n - 1];
    }
    return ans;
  };

  vector<mint> ans;
  ans.push_back(get_ans());

  vector ndp(n, vector<mint>(n));
  vector<mint> sum(n);
  while (len(ans) <= k && double(clock()) / CLOCKS_PER_SEC < 2.5 && len(ans) <= 3e4) {
    for (auto &v : ndp) {
        for (auto &x : v) {
            x = 0;
        }
    }
    for (auto &x : sum) {
        x = 0;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            sum[j] += dp[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (!g[i][j]) {
                continue;
            }
            ndp[i][j] = sum[i];
            ndp[i][j] -= dp[j][i];
        }
    }
    dp.swap(ndp);
    ans.push_back(get_ans());
  }

  if (len(ans) > k) {
    cout << ans[k] << '\n';
    return 0;
  }

//   auto res = berlekamp_massey::find_recurrence(ans);
//   cout << res.size() << endl;
//   for (auto x : res) cout << x << ' '; cout << endl;
//   cout << berlekamp_massey::find_kth(ans, res, k) << '\n';

  const auto [P, Q] = rational_function_approximation(Poly<mint>(ans.rbegin(), ans.rend()),
                                                        Poly<mint>{mint(1)} << ans.size(), ans.size());
  const auto res    = Q / Poly<mint>{Q.lc()};

  vector<int> aa(res.deg()), rr(res.deg());
  for (int i = 0; i < res.deg(); i++) {
    aa[i] = ans[i].val();
    rr[i] =  (-res[res.deg() - 1 - i]).val();
  }

//   cout << res.deg() << endl;
//   for (auto x : rr) cout << x << ' '; cout << endl;
//   for (auto x : aa) cout << x << ' '; cout << endl;

  cout << lol::solve(res.deg(), k, aa, rr) << '\n';
  return 0;
}