#include <bits/stdc++.h>

#ifdef HOME
#define db(x) cerr << #x << " = " << x << endl
#define db3(x, y, z) cerr << "(" << #x << ", " << #y << ", " << #z << ") = (" << x << ", " << y << ", " << z << ")" << endl
#define db2(x, y) cerr << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")" << endl
#define dbv(a) cerr << #a << " = "; for (auto xxx: a) cerr << xxx  << " "; cerr << endl
#else
#define db(x) ;
#define db3(x, y, z) ;
#define db2(x, y) ;
#define dbv(a) ;
#endif

using namespace std;
typedef long long ll;
typedef double dbl;


const ll INF = 1.01e18;





namespace n_mint {
    template<typename T>
    T inverse(T a, T m) {
        T u = 0, v = 1;
        while (a != 0) {
            T t = m / a;
            m -= t * a;
            swap(a, m);
            u -= t * v;
            swap(u, v);
        }
        assert(m == 1);
        return u;
    }
    template<typename T>
    class MMint {
    public:
        using Arg = T;
        using Type = typename decay<decltype(T::value)>::type;
        constexpr MMint() : value() {}
        template<typename U>
        MMint(const U &x) {
            value = normalize(x);
        }
        template<typename U>
        static Type normalize(const U &x) {
            Type v;
            if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
            else v = static_cast<Type>(x % mod());
            if (v < 0) v += mod();
            return v;
        }
        const Type &operator()() const { return value; }
        template<typename U>
        explicit operator U() const { return static_cast<U>(value); }
        constexpr static Type mod() { return T::value; }
        MMint &operator+=(const MMint &other) {
            if ((value += other.value) >= mod()) value -= mod();
            return *this;
        }
        MMint &operator-=(const MMint &other) {
            if ((value -= other.value) < 0) value += mod();
            return *this;
        }
        template<typename U>
        MMint &operator+=(const U &other) { return *this += MMint(other); }
        template<typename U>
        MMint &operator-=(const U &other) { return *this -= MMint(other); }
        MMint &operator++() { return *this += 1; }
        MMint &operator--() { return *this -= 1; }
        const MMint operator++(int) {
            MMint result(*this);
            *this += 1;
            return result;
        }
        const MMint operator--(int) {
            MMint result(*this);
            *this -= 1;
            return result;
        }
        MMint operator-() const { return MMint(-value); }
        template<typename U = T>
        typename enable_if<is_same<typename MMint<U>::Type, int>::value, MMint>::type &operator*=(const MMint &rhs) {
            value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
            return *this;
        }
        template<typename U = T>
        typename enable_if<is_same<typename MMint<U>::Type, int64_t>::value, MMint>::type &operator*=(const MMint &rhs) {
            auto q = static_cast<int64_t>(static_cast<long double>(value) * rhs.value / mod());
            value = normalize(value * rhs.value - q * mod());
            return *this;
        }
        template<typename U = T>
        typename enable_if<!is_integral<typename MMint<U>::Type>::value, MMint>::type &operator*=(const MMint &rhs) {
            value = normalize(value * rhs.value);
            return *this;
        }
        MMint &operator/=(const MMint &other) { return *this *= MMint(inverse(other.value, mod())); }
        MMint inv() const { return MMint(inverse(value, mod())); }
        template<typename U>
        friend bool operator==(const MMint<U> &lhs, const MMint<U> &rhs);
        template<typename U>
        friend bool operator<(const MMint<U> &lhs, const MMint<U> &rhs);
        template<typename U>
        friend bool operator>(const MMint<U> &lhs, const MMint<U> &rhs);
        template<typename U>
        friend std::istream &operator>>(std::istream &stream, MMint<U> &number);
    private:
        Type value;
    };
    template<typename T>
    MMint<T> abs(const MMint<T> &val) { return val; }
    template<typename T>
    bool operator==(const MMint<T> &lhs, const MMint<T> &rhs) { return lhs.value == rhs.value; }
    template<typename T, typename U>
    bool operator==(const MMint<T> &lhs, U rhs) { return lhs == MMint<T>(rhs); }
    template<typename T, typename U>
    bool operator==(U lhs, const MMint<T> &rhs) { return MMint<T>(lhs) == rhs; }
    template<typename T>
    bool operator!=(const MMint<T> &lhs, const MMint<T> &rhs) { return !(lhs == rhs); }
    template<typename T, typename U>
    bool operator!=(const MMint<T> &lhs, U rhs) { return !(lhs == rhs); }
    template<typename T, typename U>
    bool operator!=(U lhs, const MMint<T> &rhs) { return !(lhs == rhs); }
    template<typename T>
    bool operator<(const MMint<T> &lhs, const MMint<T> &rhs) { return lhs.value < rhs.value; }
    template<typename T>
    bool operator>(const MMint<T> &lhs, const MMint<T> &rhs) { return lhs.value > rhs.value; }
    template<typename T>
    MMint<T> operator+(const MMint<T> &lhs, const MMint<T> &rhs) { return MMint<T>(lhs) += rhs; }
    template<typename T, typename U>
    MMint<T> operator+(const MMint<T> &lhs, U rhs) { return MMint<T>(lhs) += rhs; }
    template<typename T, typename U>
    MMint<T> operator+(U lhs, const MMint<T> &rhs) { return MMint<T>(lhs) += rhs; }
    template<typename T>
    MMint<T> operator-(const MMint<T> &lhs, const MMint<T> &rhs) { return MMint<T>(lhs) -= rhs; }
    template<typename T, typename U>
    MMint<T> operator-(const MMint<T> &lhs, U rhs) { return MMint<T>(lhs) -= rhs; }
    template<typename T, typename U>
    MMint<T> operator-(U lhs, const MMint<T> &rhs) { return MMint<T>(lhs) -= rhs; }
    template<typename T>
    MMint<T> operator*(const MMint<T> &lhs, const MMint<T> &rhs) { return MMint<T>(lhs) *= rhs; }
    template<typename T, typename U>
    MMint<T> operator*(const MMint<T> &lhs, U rhs) { return MMint<T>(lhs) *= rhs; }
    template<typename T, typename U>
    MMint<T> operator*(U lhs, const MMint<T> &rhs) { return MMint<T>(lhs) *= rhs; }
    template<typename T>
    MMint<T> operator/(const MMint<T> &lhs, const MMint<T> &rhs) { return MMint<T>(lhs) /= rhs; }
    template<typename T, typename U>
    MMint<T> operator/(const MMint<T> &lhs, U rhs) { return MMint<T>(lhs) /= rhs; }
    template<typename T, typename U>
    MMint<T> operator/(U lhs, const MMint<T> &rhs) { return MMint<T>(lhs) /= rhs; }
    template<typename T, typename U>
    MMint<T> bin(const MMint<T> &a, const U &b) {
        assert(b >= 0);
        MMint<T> x = a, res = 1;
        U p = b;
        while (p > 0) {
            if (p & 1) res *= x;
            x *= x;
            p >>= 1;
        }
        return res;
    }
    template <typename T>
    MMint<T> inv(const MMint<T> &a) {
        return inverse(a(), MMint<T>::mod());
    }
    template<typename T>
    string to_string(const MMint<T> &number) {
        return std::to_string(number());
    }
    template<typename T>
    std::ostream &operator<<(std::ostream &stream, const MMint<T> &number) {
        return stream << number();
    }
    template<typename T>
    std::istream &operator>>(std::istream &stream, MMint<T> &number) {
        typename common_type<typename MMint<T>::Type, int64_t>::type x;
        stream >> x;
        number.value = MMint<T>::normalize(x);
        return stream;
    }
    template<typename T, typename Enabled = void>
    struct is_modular : std::false_type {};
    template<typename T>
    struct is_modular<T, typename enable_if<
            is_same<T, MMint<typename T::Arg>>::value &&
            is_integral<typename T::Type>::value
    >::type> : true_type {};
    struct DynamicMod {
        static int value;
    };
    constexpr int MOD = 998244353;
    using mint = MMint<std::integral_constant<decay<decltype(MOD)>::type, MOD>>;
}
using namespace n_mint;
namespace n_ffti {
    struct ffti {
        static std::vector<mint> root;
        static std::vector<int> rev;
        static int N;
        static void prepRoots() {
            static int lastMod = 0;
            if (mint::mod() == lastMod && (int) root.size() >= N) return;
            lastMod = mint::mod();
            int cN = max(N, 1 << 17);
            rev.resize(cN);
            root.resize(cN);
            for (int i = 1; i < cN; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * (cN / 2));
            mint croot = 2;
            while (!(bin(croot, cN) == mint(1) && bin(croot, cN / 2) != mint(1))) croot++;
            mint cur = 1;
            for (int i = cN >> 1; i < cN; i++) {
                root[i] = cur;
                cur *= croot;
            }
            for (int i = (cN >> 1) - 1; i >= 1; i--) {
                root[i] = root[i * 2];
            }
        }
        static void prepAB(std::vector<mint> &A, std::vector<mint> &B) {
            N = 1;
            while (N < (int) (A.size() + B.size())) N <<= 1;
            while ((int) A.size() < N) A.push_back(0);
            while ((int) B.size() < N) B.push_back(0);
            prepRoots();
        }
        static void fft(std::vector<mint> &f) {
            for (int i = 0; i < N; i++) {
                int j = rev[i] >> __builtin_ctz(root.size() / N);
                if (i < j) std::swap(f[i], f[j]);
            }
            for (int k = 1; k < N; k <<= 1) {
                for (int i = 0; i < N; i += 2 * k) {
                    for (int j = 0; j < k; j++) {
                        mint z = f[i + k + j] * root[k + j];
                        f[i + j + k] = f[i + j] - z;
                        f[i + j] = f[i + j] + z;
                    }
                }
            }
        }
        static std::vector<mint> mul(std::vector<mint> a, std::vector<mint> b) {
            int rsz = a.size() + b.size() - 1;
            bool eq = a == b;
            prepAB(a, b);
            fft(a);
            if (eq) {
                b = a;
            } else {
                fft(b);
            }
            mint oN = mint(N).inv();
            for (int i = 0; i < N; i++) {
                a[i] = a[i] * b[i] * oN;
            }
            reverse(a.begin() + 1, a.begin() + N);
            fft(a);
            a.resize(rsz);
            return a;
        }
    };
    std::vector<mint> ffti::root;
    std::vector<int> ffti::rev;
    int ffti::N;
}
using namespace n_ffti;

namespace n_fftd {
    struct num {
        double x, y;
        num() {}
        num(double xx, double yy) : x(xx), y(yy) {}
        num(double alp) : x(cos(alp)), y(sin(alp)) {}
    };
    inline num operator+(const num &a, const num &b) { return num(a.x + b.x, a.y + b.y); }
    inline num operator-(const num &a, const num &b) { return num(a.x - b.x, a.y - b.y); }
    inline num operator*(const num &a, const num &b) { return num(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x); }
    inline num conj(num a) { return num(a.x, -a.y); }
    struct fftd {
    private:
        static constexpr double PI = M_PI;
        static std::vector<num> root;
        static std::vector<int> rev;
        static std::vector<num> a, b;
        static int N;
        static void prepRoots() {
            if ((int) root.size() >= N) return;
            int old = root.size();
            root.resize(N);
            if (old == 0) {
                if (root.size() < 2) root.resize(2);
                root[1] = num(1, 0);
            }
            for (int k = 1; (1 << k) < N; k++) {
                if ((1 << k) < old) continue;
                num x(2 * PI / (1LL << (k + 1)));
                for (int i = (1LL << (k - 1)); i < (1LL << (k)); i++) {
                    root[2 * i] = root[i];
                    root[2 * i + 1] = root[i] * x;
                }
            }
            rev.resize(N);
            for (int i = 1; i < N; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * (N / 2));
        }
        template<typename T>
        static void prepAB(std::vector<T> &A, std::vector<T> &B) {
            N = 1;
            while (N < (int) (A.size() + B.size())) N <<= 1;
            while ((int) A.size() < N) A.push_back(0);
            while ((int) B.size() < N) B.push_back(0);
            prepRoots();
        }
        static void fft(std::vector<num> &f) {
            for (int i = 0; i < N; i++) {
                int j = rev[i] >> __builtin_ctz(root.size() / N);
                if (i < j) std::swap(f[i], f[j]);
            }
            for (int k = 1; k < N; k <<= 1) {
                for (int i = 0; i < N; i += 2 * k) {
                    for (int j = 0; j < k; j++) {
                        num z = f[i + j + k] * root[j + k];
                        f[i + j + k] = f[i + j] - z;
                        f[i + j] = f[i + j] + z;
                    }
                }
            }
        }
        template<typename T>
        static std::vector<T> mulSingle(std::vector<T> A, std::vector<T> B) {
            int rsz = A.size() + B.size() - 1;
            prepAB(A, B);
            if ((int) a.size() < N) a.resize(N);
            for (int i = 0; i < N; i++) a[i] = num((double) A[i], (double) B[i]);
            fft(a);
            for (int i = 0; i <= N / 2; i++) {
                int j = (N - i) & (N - 1);
                num x = (a[j] * a[j] - conj(a[i] * a[i])) * num(0, -0.25 / N);
                num y = (a[i] * a[i] - conj(a[j] * a[j])) * num(0, -0.25 / N);
                a[i] = x;
                if (j != i) a[j] = y;
            }
            fft(a);
            std::vector<T> C(N);
            for (int i = 0; i < N; i++) {
                if (is_floating_point<T>::value) {
                    C[i] = a[i].x;
                } else {
                    C[i] = (T)(long long)round(a[i].x);
                }
            }
            C.resize(rsz);
            return C;
        }
        struct PossibleTypes {
            struct Modular {};
            struct NonModular {};
        };
        template<typename T, typename Enabled = void>
        struct GetType {
            using Type = PossibleTypes::NonModular;
        };
        template<typename T>
        struct GetType<T, typename enable_if<is_modular<T>::value>::type> {
            using Type = PossibleTypes::Modular;
        };
        template<typename T>
        static std::vector<T> mul(const std::vector<T> &A, const std::vector<T> &B, PossibleTypes::Modular) {
            return mulMod(A, B, T::mod());
        }
        template<typename T>
        static std::vector<T> mul(const std::vector<T> &A, const std::vector<T> &B, PossibleTypes::NonModular) {
            return mulSingle(A, B);
        }
    public:
        template<typename T>
        static std::vector<T> mulMod(std::vector<T> A, std::vector<T> B, int CUR_MOD) {
            int rsz = A.size() + B.size() - 1;
            prepAB(A, B);
            if ((int) a.size() < N) a.resize(N);
            for (int i = 0; i < N; i++) {
                int x = A[i];
                a[i] = num(x & ((1 << 15) - 1), x >> 15);
            }
            fft(a);
            if (A == B) {
                b = a;
            } else {
                if ((int) b.size() < N) b.resize(N);
                for (int i = 0; i < N; i++) {
                    int x = B[i];
                    b[i] = num(x & ((1 << 15) - 1), x >> 15);
                }
                fft(b);
            }
            for (int i = 0; i <= N / 2; i++) {
                int j = (N - i) & (N - 1);
                num a1 = (a[i] + conj(a[j])) * num(0.5, 0);
                num a2 = (a[i] - conj(a[j])) * num(0, -0.5);
                num b1 = (b[i] + conj(b[j])) * num(0.5 / N, 0);
                num b2 = (b[i] - conj(b[j])) * num(0, -0.5 / N);
                if (i != j) {
                    num aa1 = (a[j] + conj(a[i])) * num(0.5, 0);
                    num aa2 = (a[j] - conj(a[i])) * num(0, -0.5);
                    num bb1 = (b[j] + conj(b[i])) * num(0.5 / N, 0);
                    num bb2 = (b[j] - conj(b[i])) * num(0, -0.5 / N);
                    a[i] = aa1 * bb1 + aa2 * bb2 * num(0, 1);
                    b[i] = aa1 * bb2 + aa2 * bb1;
                }
                a[j] = a1 * b1 + a2 * b2 * num(0, 1);
                b[j] = a1 * b2 + a2 * b1;
            }
            fft(a);
            fft(b);
            std::vector<T> C(N);
            for (int i = 0; i < N; i++) {
                long long aa = a[i].x + 0.5;
                long long bb = b[i].x + 0.5;
                long long cc = a[i].y + 0.5;
                C[i] = (aa + bb % CUR_MOD * (1LL << 15) + cc % CUR_MOD * (1LL << 30)) % CUR_MOD;
            }
            C.resize(rsz);
            return C;
        }
        template<typename T>
        static std::vector<T> mul(const std::vector<T> &A, const std::vector<T> &B) {
            using CurType = typename GetType<T>::Type;
            return mul(A, B, CurType());
        }
    };
    std::vector<num> fftd::root;
    std::vector<int> fftd::rev;
    std::vector<num> fftd::a, fftd::b;
    int fftd::N;
}
using namespace n_fftd;
template <typename T, typename FFT = fftd>
struct fft_online {
    vector<T> a, b, c;
    fft_online(vector<T> _a) : a(_a) {}
    T add(int k, T x) {
        if ((int)c.size() < 3 * (k + 1)) {
            a.resize(max((int)a.size(), 4 * (k + 1)));
            b.resize(max((int)b.size(), 4 * (k + 1)));
            c.resize(max((int)c.size(), 4 * (k + 1)));
        }
        b[k] = x;
        c[k] += a[0] * b[k];
        int z = 1;
        while ((k & (z - 1)) == (z - 1)) {
            vector<T> ca(z), cb(z);
            for (int i = 0; i < z; i++) ca[i] = a[z + i];
            for (int i = 0; i < z; i++) cb[i] = b[k - z + 1 + i];
            auto cc = FFT::mul(ca, cb);
            for (int i = 0; i < 2 * z - 1; i++) c[k + 1 + i] += cc[i];
            z <<= 1;
        }
        return c[k];
    }
};
template <typename T, typename FFT = fftd>
struct poly : vector<T> {
    using vector<T>::vector;
    poly(const vector<T> &a) : vector<T>(a) {}
    explicit poly(int x) : vector<T>(x) {}
    friend ostream& operator<< (ostream& out, const poly& p) {
        out << p.to_string();
        return out;
    }
    poly& operator+= (const poly &p) {
        this->resize(max(this->size(), p.size()));
        for (int i = 0; i < (int)p.size(); i++) {
            (*this)[i] += p[i];
        }
        return *this;
    }
    friend poly operator+ (poly a, const poly &b) {
        return a += b;
    }
    poly& operator-= (const poly &p) {
        this->resize(max(this->size(), p.size()));
        for (int i = 0; i < (int)p.size(); i++) {
            (*this)[i] -= p[i];
        }
        return *this;
    }
    friend poly operator- (poly a, const poly &b) {
        return a -= b;
    }
    poly& operator*= (T d) {
        for (int i = 0; i < (int)this->size(); i++) {
            (*this)[i] *= d;
        }
        return *this;
    }
    friend poly operator* (poly a, T d) {
        return a *= d;
    }
    poly& operator/= (T d) {
        auto od = T(1) / d;
        for (int i = 0; i < (int)this->size(); i++) {
            (*this)[i] *= od;
        }
        return *this;
    }
    friend poly operator/ (poly a, T d) {
        return a /= d;
    }
    static poly slow_mul(const poly &a, const poly &b) {
        poly res(a.size() + b.size() - 1);
        for (int i = 0; i < (int)a.size(); i++) {
            for (int j = 0; j < (int)b.size(); j++) {
                res[i + j] += a[i] * b[j];
            }
        }
        return res;
    }
    poly& operator*= (const poly &p) {
        if (min(this->size(), p.size()) <= 100) {
            *this = slow_mul(*this, p);
        } else {
            *this = poly(FFT::mul(*this, p));
        }
        return *this;
    }
    friend poly operator* (poly a, const poly &b) {
        return a *= b;
    }
    poly inv() const {
        assert((*this)[0] != 0);
        poly r({T(1) / (*this)[0]});
        for (int n = 1; n < (int)this->size(); n <<= 1) {
            poly ca = cut(2 * n);
            r = (r * 2 - r * r * ca).cut(2 * n);
        }
        r.resize(this->size());
        return r;
    }
    poly sqrt() const {
        assert((*this)[0] == 1);
        poly r(1, 1);
        for (int n = 1; n < (int)this->size(); n <<= 1) {
            poly ca = cut(2 * n);
            r = ((r + ca * r.cut(2 * n).inv()) / 2).cut(2 * n);
        }
        r.resize(this->size());
        return r;
    }
    void norm() {
        while (this->size() > 1 && this->back() == 0) {
            this->pop_back();
        }
    }
    poly rev() const {
        return poly(this->rbegin(), this->rend());
    }
    poly cut(int n) const {
        poly res = *this;
        res.resize(n);
        return res;
    }
    pair<poly, poly> div(poly b) const {
        auto a = *this;
        a.norm(); b.norm();
        if (a.size() < b.size()) return make_pair(poly({0}), a);
        T x = b.back();
        assert(x != 0);
        b /= x;
        auto rb = b.rev().cut(a.size() - b.size() + 1);
        auto q = (rb.inv() * a.rev()).cut(a.size() - b.size() + 1).rev();
        poly r = a - b * q;
        q /= x;
        r.norm();
        return {q, r};
    }
    friend poly operator/ (poly a, const poly &b) {
        return a /= b;
    }
    poly& operator/= (const poly &p) {
        return *this = div(p).first;
    }
    friend poly operator% (poly a, const poly &b) {
        return a %= b;
    }
    poly& operator%= (const poly &p) {
        return *this = div(p).second;
    }
    poly derivative() const {
        poly res(max(1, (int)this->size() - 1), 0);
        for (int i = 1; i < (int)this->size(); i++) res[i - 1] = (*this)[i] * i;
        return res;
    }
    poly integrate() const {
        poly res(this->size() + 1);
        for (int i = 1; i < (int)res->size(); i++) {
            res[i] = (*this)[i - 1] / i;
        }
        return res;
    }
    poly exp() const {
        assert((*this)[0] == 0);
        fft_online<T, FFT> t(derivative());
        vector<T> g(this->size());
        g[0] = T(1);
        for (int i = 1; i < (int)g.size(); i++) {
            int x = t.add(i - 1, g[i - 1]);
            g[i] = x / T(i);
        }
        return g;
    }
    T eval(T x) const {
        T res = 0;
        for (int i = (int)this->size() - 1; i >= 0; i--) {
            res = res * x + (*this)[i];
        }
        return res;
    }
    vector<T> eval(const vector<T> &x) {
        int m = x.size();
        vector<poly> t(4 * m);
        function<poly(int, int, int)> prod = [&](int v, int l, int r) {
            poly res;
            if (l == r) {
                res = poly({-x[l], 1});
            } else {
                int m = (l + r) >> 1;
                res = prod(v * 2, l, m) * prod(v * 2 + 1, m + 1, r);
            }
            return t[v] = res;
        };
        prod(1, 0, m - 1);
        vector<T> ans(m);
        function<void(poly, int, int, int)> eval = [&](poly cur, int v, int l, int r) {
            cur %= t[v];
            if (r - l <= 500) {
                for (int i = l; i <= r; i++) {
                    ans[i] = cur.eval(x[i]);
                }
            } else {
                int m = (l + r) >> 1;
                eval(cur, v * 2, l, m);
                eval(cur, v * 2 + 1, m + 1, r);
            }
        };
        eval(*this, 1, 0, m - 1);
        return ans;
    }
    string to_string() const {
        string res;
        for (int i = 0; i < (int)this->size(); i++) {
            res += ::to_string((*this)[i]);
            if (i + 1 < (int)this->size()) res += " ";
        }
        return res;
    }
};

template <typename T>
poly<T> mul(poly<T> a, const poly<T> &b, int coefs) {
    a *= b;
    a.resize(coefs);
    return a;
}

template <typename T>
poly<T> bin(poly<T> a, ll n, int coefs) {
    poly<T> res({1});
    while (n) {
        if (n & 1) res = mul(res, a, coefs);
        a = mul(a, a, coefs);
        n >>= 1;
    }
    return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {
    return '"' + s + '"';
}

string to_string(const char* s) {
    return to_string((string) s);
}

string to_string(bool b) {
    return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
    bool first = true;
    string res = "{";
    for (int i = 0; i < static_cast<int>(v.size()); i++) {
        if (!first) {
            res += ", ";
        }
        first = false;
        res += to_string(v[i]);
    }
    res += "}";
    return res;
}

template <size_t N>
string to_string(bitset<N> v) {
    string res = "";
    for (size_t i = 0; i < N; i++) {
        res += static_cast<char>('0' + v[i]);
    }
    return res;
}

template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for (const auto &x : v) {
        if (!first) {
            res += ", ";
        }
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
    return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
    return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << to_string(H);
    debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

template <typename T>
class Modular {
public:
    using Type = typename decay<decltype(T::value)>::type;

    constexpr Modular() : value() {}
    template <typename U>
    Modular(const U& x) {
        value = normalize(x);
    }

    template <typename U>
    static Type normalize(const U& x) {
        Type v;
        if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
        else v = static_cast<Type>(x % mod());
        if (v < 0) v += mod();
        return v;
    }

    const Type& operator()() const { return value; }
    template <typename U>
    explicit operator U() const { return static_cast<U>(value); }
    constexpr static Type mod() { return T::value; }

    Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; }
    Modular& operator-=(const Modular& other) { if ((value -= other.value) < 0) value += mod(); return *this; }
    template <typename U> Modular& operator+=(const U& other) { return *this += Modular(other); }
    template <typename U> Modular& operator-=(const U& other) { return *this -= Modular(other); }
    Modular& operator++() { return *this += 1; }
    Modular& operator--() { return *this -= 1; }
    Modular operator++(int) { Modular result(*this); *this += 1; return result; }
    Modular operator--(int) { Modular result(*this); *this -= 1; return result; }
    Modular operator-() const { return Modular(-value); }

    template <typename U = T>
    typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
#ifdef _WIN32
        uint64_t x = static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value);
    uint32_t xh = static_cast<uint32_t>(x >> 32), xl = static_cast<uint32_t>(x), d, m;
    asm(
      "divl %4; \n\t"
      : "=a" (d), "=d" (m)
      : "d" (xh), "a" (xl), "r" (mod())
    );
    value = m;
#else
        value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
#endif
        return *this;
    }
    template <typename U = T>
    typename enable_if<is_same<typename Modular<U>::Type, int64_t>::value, Modular>::type& operator*=(const Modular& rhs) {
        int64_t q = static_cast<int64_t>(static_cast<long double>(value) * rhs.value / mod());
        value = normalize(value * rhs.value - q * mod());
        return *this;
    }
    template <typename U = T>
    typename enable_if<!is_integral<typename Modular<U>::Type>::value, Modular>::type& operator*=(const Modular& rhs) {
        value = normalize(value * rhs.value);
        return *this;
    }

    Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }

    template <typename U>
    friend const Modular<U>& abs(const Modular<U>& v) { return v; }

    template <typename U>
    friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs);

    template <typename U>
    friend bool operator<(const Modular<U>& lhs, const Modular<U>& rhs);

    template <typename U>
    friend std::istream& operator>>(std::istream& stream, Modular<U>& number);

private:
    Type value;
};

template <typename T> bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value == rhs.value; }
template <typename T, typename U> bool operator==(const Modular<T>& lhs, U rhs) { return lhs == Modular<T>(rhs); }
template <typename T, typename U> bool operator==(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) == rhs; }

template <typename T> bool operator!=(const Modular<T>& lhs, const Modular<T>& rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(const Modular<T>& lhs, U rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(U lhs, const Modular<T>& rhs) { return !(lhs == rhs); }

template <typename T> bool operator<(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value < rhs.value; }

template <typename T> Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }

template <typename T> Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }

template <typename T> Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }

template <typename T> Modular<T> operator/(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U> Modular<T> operator/(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U> Modular<T> operator/(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }

template<typename T, typename U>
Modular<T> power(const Modular<T>& a, const U& b) {
    assert(b >= 0);
    Modular<T> x = a, res = 1;
    U p = b;
    while (p > 0) {
        if (p & 1) res *= x;
        x *= x;
        p >>= 1;
    }
    return res;
}

template <typename T>
bool IsZero(const Modular<T>& number) {
    return number() == 0;
}

template <typename T>
string to_string(const Modular<T>& number) {
    return to_string(number());
}

template <typename T>
std::ostream& operator<<(std::ostream& stream, const Modular<T>& number) {
    return stream << number();
}

template <typename T>
std::istream& operator>>(std::istream& stream, Modular<T>& number) {
    typename common_type<typename Modular<T>::Type, int64_t>::type x;
    stream >> x;
    number.value = Modular<T>::normalize(x);
    return stream;
}


constexpr int md = 998244353;
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;

vector<Mint> fact;
vector<Mint> inv_fact;

template <typename T>
class NTT {
public:
    using Type = typename decay<decltype(T::value)>::type;

    static Type md;
    static Modular<T> root;
    static int base;
    static int max_base;
    static vector<Modular<T>> roots;
    static vector<int> rev;

    static void clear() {
        root = 0;
        base = 0;
        max_base = 0;
        roots.clear();
        rev.clear();
    }

    static void init() {
        md = T::value;
        assert(md >= 3 && md % 2 == 1);
        auto tmp = md - 1;
        max_base = 0;
        while (tmp % 2 == 0) {
            tmp /= 2;
            max_base++;
        }
        root = 2;
        while (power(root, (md - 1) >> 1) == 1) {
            root++;
        }
        assert(power(root, md - 1) == 1);
        root = power(root, (md - 1) >> max_base);
        base = 1;
        rev = {0, 1};
        roots = {0, 1};
    }

    static void ensure_base(int nbase) {
        if (md != T::value) {
            clear();
        }
        if (roots.empty()) {
            init();
        }
        if (nbase <= base) {
            return;
        }
        assert(nbase <= max_base);
        rev.resize(1 << nbase);
        for (int i = 0; i < (1 << nbase); i++) {
            rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (nbase - 1));
        }
        roots.resize(1 << nbase);
        while (base < nbase) {
            Modular<T> z = power(root, 1 << (max_base - 1 - base));
            for (int i = 1 << (base - 1); i < (1 << base); i++) {
                roots[i << 1] = roots[i];
                roots[(i << 1) + 1] = roots[i] * z;
            }
            base++;
        }
    }

    static void fft(vector<Modular<T>> &a) {
        int n = (int) a.size();
        assert((n & (n - 1)) == 0);
        int zeros = __builtin_ctz(n);
        ensure_base(zeros);
        int shift = base - zeros;
        for (int i = 0; i < n; i++) {
            if (i < (rev[i] >> shift)) {
                swap(a[i], a[rev[i] >> shift]);
            }
        }
        for (int k = 1; k < n; k <<= 1) {
            for (int i = 0; i < n; i += 2 * k) {
                for (int j = 0; j < k; j++) {
                    Modular<T> x = a[i + j];
                    Modular<T> y = a[i + j + k] * roots[j + k];
                    a[i + j] = x + y;
                    a[i + j + k] = x - y;
                }
            }
        }
    }

    static vector<Modular<T>> multiply(vector<Modular<T>> a, vector<Modular<T>> b) {
        if (a.empty() || b.empty()) {
            return {};
        }
        int eq = (a == b);
        int need = (int) a.size() + (int) b.size() - 1;
        int nbase = 0;
        while ((1 << nbase) < need) nbase++;
        ensure_base(nbase);
        int sz = 1 << nbase;
        a.resize(sz);
        b.resize(sz);
        fft(a);
        if (eq) b = a; else fft(b);
        Modular<T> inv_sz = 1 / static_cast<Modular<T>>(sz);
        for (int i = 0; i < sz; i++) {
            a[i] *= b[i] * inv_sz;
        }
        reverse(a.begin() + 1, a.end());
        fft(a);
        a.resize(need);
        return a;
    }
};

template <typename T> typename NTT<T>::Type NTT<T>::md;
template <typename T> Modular<T> NTT<T>::root;
template <typename T> int NTT<T>::base;
template <typename T> int NTT<T>::max_base;
template <typename T> vector<Modular<T>> NTT<T>::roots;
template <typename T> vector<int> NTT<T>::rev;

template <typename T>
vector<Modular<T>> inverse(const vector<Modular<T>>& a) {
    assert(!a.empty());
    int n = (int) a.size();
    vector<Modular<T>> b = {1 / a[0]};
    while ((int) b.size() < n) {
        vector<Modular<T>> x(a.begin(), a.begin() + min(a.size(), b.size() << 1));
        x.resize(b.size() << 1);
        b.resize(b.size() << 1);
        vector<Modular<T>> c = b;
        NTT<T>::fft(c);
        NTT<T>::fft(x);
        Modular<T> inv = 1 / static_cast<Modular<T>>((int) x.size());
        for (int i = 0; i < (int) x.size(); i++) {
            x[i] *= c[i] * inv;
        }
        reverse(x.begin() + 1, x.end());
        NTT<T>::fft(x);
        rotate(x.begin(), x.begin() + (x.size() >> 1), x.end());
        fill(x.begin() + (x.size() >> 1), x.end(), 0);
        NTT<T>::fft(x);
        for (int i = 0; i < (int) x.size(); i++) {
            x[i] *= c[i] * inv;
        }
        reverse(x.begin() + 1, x.end());
        NTT<T>::fft(x);
        for (int i = 0; i < ((int) x.size() >> 1); i++) {
            b[i + ((int) x.size() >> 1)] = -x[i];
        }
    }
    b.resize(n);
    return b;
}

template <typename T>
vector<Modular<T>> inverse_old(vector<Modular<T>> a) {
    assert(!a.empty());
    int n = (int) a.size();
    if (n == 1) {
        return {1 / a[0]};
    }
    int m = (n + 1) >> 1;
    vector<Modular<T>> b = inverse(vector<Modular<T>>(a.begin(), a.begin() + m));
    int need = n << 1;
    int nbase = 0;
    while ((1 << nbase) < need) {
        ++nbase;
    }
    NTT<T>::ensure_base(nbase);
    int size = 1 << nbase;
    a.resize(size);
    b.resize(size);
    NTT<T>::fft(a);
    NTT<T>::fft(b);
    Modular<T> inv = 1 / static_cast<Modular<T>>(size);
    for (int i = 0; i < size; ++i) {
        a[i] = (2 - a[i] * b[i]) * b[i] * inv;
    }
    reverse(a.begin() + 1, a.end());
    NTT<T>::fft(a);
    a.resize(n);
    return a;
}

template <typename T>
vector<Modular<T>> operator*(const vector<Modular<T>>& a, const vector<Modular<T>>& b) {
    if (a.empty() || b.empty()) {
        return {};
    }
    if (min(a.size(), b.size()) < 150) {
        vector<Modular<T>> c(a.size() + b.size() - 1, 0);
        for (int i = 0; i < (int) a.size(); i++) {
            for (int j = 0; j < (int) b.size(); j++) {
                c[i + j] += a[i] * b[j];
            }
        }
        return c;
    }
    return NTT<T>::multiply(a, b);
}

template <typename T>
vector<Modular<T>>& operator*=(vector<Modular<T>>& a, const vector<Modular<T>>& b) {
    return a = a * b;
}

template <typename T>
vector<T>& operator+=(vector<T>& a, const vector<T>& b) {
    if (a.size() < b.size()) {
        a.resize(b.size());
    }
    for (int i = 0; i < (int) b.size(); i++) {
        a[i] += b[i];
    }
    return a;
}

template <typename T>
vector<T> operator+(const vector<T>& a, const vector<T>& b) {
    vector<T> c = a;
    return c += b;
}

template <typename T>
vector<T>& operator-=(vector<T>& a, const vector<T>& b) {
    if (a.size() < b.size()) {
        a.resize(b.size());
    }
    for (int i = 0; i < (int) b.size(); i++) {
        a[i] -= b[i];
    }
    return a;
}

template <typename T>
vector<T> operator-(const vector<T>& a, const vector<T>& b) {
    vector<T> c = a;
    return c -= b;
}

template <typename T>
vector<T> operator-(const vector<T>& a) {
    vector<T> c = a;
    for (int i = 0; i < (int) c.size(); i++) {
        c[i] = -c[i];
    }
    return c;
}

template <typename T>
vector<T> operator*(const vector<T>& a, const vector<T>& b) {
    if (a.empty() || b.empty()) {
        return {};
    }
    vector<T> c(a.size() + b.size() - 1, 0);
    for (int i = 0; i < (int) a.size(); i++) {
        for (int j = 0; j < (int) b.size(); j++) {
            c[i + j] += a[i] * b[j];
        }
    }
    return c;
}

template <typename T>
vector<T>& operator*=(vector<T>& a, const vector<T>& b) {
    return a = a * b;
}

template <typename T>
vector<T> inverse(const vector<T>& a) {
    assert(!a.empty());
    int n = (int) a.size();
    vector<T> b = {1 / a[0]};
    while ((int) b.size() < n) {
        vector<T> a_cut(a.begin(), a.begin() + min(a.size(), b.size() << 1));
        vector<T> x = b * b * a_cut;
        b.resize(b.size() << 1);
        for (int i = (int) b.size() >> 1; i < (int) min(x.size(), b.size()); i++) {
            b[i] = -x[i];
        }
    }
    b.resize(n);
    return b;
}

template <typename T>
vector<T>& operator/=(vector<T>& a, const vector<T>& b) {
    int n = (int) a.size();
    int m = (int) b.size();
    if (n < m) {
        a.clear();
    } else {
        vector<T> d = b;
        reverse(a.begin(), a.end());
        reverse(d.begin(), d.end());
        d.resize(n - m + 1);
        a *= inverse(d);
        a.erase(a.begin() + n - m + 1, a.end());
        reverse(a.begin(), a.end());
    }
    return a;
}

template <typename T>
vector<T> operator/(const vector<T>& a, const vector<T>& b) {
    vector<T> c = a;
    return c /= b;
}

template <typename T>
vector<T>& operator%=(vector<T>& a, const vector<T>& b) {
    int n = (int) a.size();
    int m = (int) b.size();
    if (n >= m) {
        vector<T> c = (a / b) * b;
        a.resize(m - 1);
        for (int i = 0; i < m - 1; i++) {
            a[i] -= c[i];
        }
    }
    return a;
}

template <typename T>
vector<T> operator%(const vector<T>& a, const vector<T>& b) {
    vector<T> c = a;
    return c %= b;
}

template <typename T, typename U>
vector<T> power(const vector<T>& a, const U& b, const vector<T>& c) {
    assert(b >= 0);
    vector<U> binary;
    U bb = b;
    while (bb > 0) {
        binary.push_back(bb & 1);
        bb >>= 1;
    }
    vector<T> res = vector<T>{1} % c;
    for (int j = (int) binary.size() - 1; j >= 0; j--) {
        res = res * res % c;
        if (binary[j] == 1) {
            res = res * a % c;
        }
    }
    return res;
}

template <typename T>
vector<T> derivative(const vector<T>& a) {
    vector<T> c = a;
    for (int i = 0; i < (int) c.size(); i++) {
        c[i] *= i;
    }
    if (!c.empty()) {
        c.erase(c.begin());
    }
    return c;
}

template <typename T>
vector<T> primitive(const vector<T>& a) {
    vector<T> c = a;
    c.insert(c.begin(), 0);
    for (int i = 1; i < (int) c.size(); i++) {
        c[i] /= i;
    }
    return c;
}

template <typename T>
vector<T> logarithm(const vector<T>& a) {
    assert(!a.empty() && a[0] == 1);
    vector<T> u = primitive(derivative(a) * inverse(a));
    u.resize(a.size());
    return u;
}

template <typename T>
vector<T> exponent(const vector<T>& a) {
    assert(!a.empty() && a[0] == 0);
    int n = (int) a.size();
    vector<T> b = {1};
    while ((int) b.size() < n) {
        vector<T> x(a.begin(), a.begin() + min(a.size(), b.size() << 1));
        x[0] += 1;
        vector<T> old_b = b;
        b.resize(b.size() << 1);
        x -= logarithm(b);
        x *= old_b;
        for (int i = (int) b.size() >> 1; i < (int) min(x.size(), b.size()); i++) {
            b[i] = x[i];
        }
    }
    b.resize(n);
    return b;
}

template <typename T>
vector<T> multiply(const vector<vector<T>>& a) {
    if (a.empty()) {
        return {0};
    }
    function<vector<T>(int, int)> mult = [&](int l, int r) {
        if (l == r) {
            return a[l];
        }
        int y = (l + r) >> 1;
        return mult(l, y) * mult(y + 1, r);
    };
    return mult(0, (int) a.size() - 1);
}


const int N = 2e6;

mint solve(int n, int m) {
    mint res;

    vector<mint> fct(N);
    fct[0] = 1;
    for (int i= 1; i < N; i++) fct[i] = fct[i - 1] * i;
    vector<mint> ofct(N);
    ofct[N - 1] = 1 / fct[N -1 ];
    for (int i =N - 2; i >= 0; i--) ofct[i] = ofct[i + 1] * (i + 1);

    auto getC = [&](int n, int k) {
        if (n < k) return mint(0);
        return fct[n] * ofct[k] * ofct[n - k];
    };

    {
        mint cur = n;
        // (1+x+...+x^m)^(n-1)
        // (1-x^(m+1))/(1-x)
//        poly<mint> d(m + 1);
        vector<Mint> d(m + 1);
        for (int i = 0; i <= m; i++) {
            d[i] = (getC(n-1, i) * (i % 2 == 0 ? 1 : -1))();
        }
        d = inverse(d);
//        d = d.inv();

//        poly<mint> d(m + 1);
//        for (int i = 0; i <= m; i++) d[i] = 1;
//        d = bin(d, n - 1, m + 1);
//        vector<Mint> d(m + 1);
//        for (int i = 0; i <= m; i++) d[i] = 1;
//        d = exponent(logarithm(d) * vector<Mint>{n-1});

        cur *= d[m]();

        res += cur;
    }

    {
        // (1+x+...+x^(m-1)) ^ n
        // (1-x^m)/(1-x)

//        poly<mint> d(2 * m + 1);
        vector<Mint> d(2 * m + 1);
        for (int i = 0; i <= 2 * m; i++) {
            d[i] = (getC(n, i) * (i % 2 == 0 ? 1 : -1))();
        }
//        d = d.inv();
        d = inverse(d);

//        poly<mint> nom(m + 1);
        vector<Mint> nom(m + 1);
        nom[0] = 1;
        nom[m] = -n;

        d *= nom;

//        poly<mint> d(2 * m + 1);
//        for (int i = 0; i < m; i++) d[i] = 1;
//        d = bin(d, n, 2 * m + 1);
//        vector<Mint> d(m + m / 2 + 1);
//        for (int i = 0; i < m; i++) d[i] = 1;
//        d = exponent(logarithm(d) * vector<Mint>{n});


        mint cur = 0;

        for (int odd = 0; odd <= min(m, n); odd++) {
            if ((m - odd) % 2) continue;
            mint coef = getC(n, odd);
            coef *= d[m + (m - odd) / 2]();
            cur += coef;
        }
        res += cur;
    }

    return res;
}


int main() {
#ifdef HOME
    assert(freopen("in", "r", stdin));
#endif

    int n, m;
    while (scanf("%d%d", &n, &m) == 2) {
        cout << solve(n, m) << endl;
    }


#ifdef HOME
    cerr << "time: " << clock() * 1.0 / CLOCKS_PER_SEC << endl;
#endif
}


Measured memory_bytes: 62512