#line 2 "/Users/noya2/Desktop/Noya2_library/template/template.hpp"
using namespace std;

#include<bits/stdc++.h>
#line 1 "/Users/noya2/Desktop/Noya2_library/template/inout_old.hpp"
namespace noya2 {

template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p){
    os << p.first << " " << p.second;
    return os;
}
template <typename T, typename U>
istream &operator>>(istream &is, pair<T, U> &p){
    is >> p.first >> p.second;
    return is;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v){
    int s = (int)v.size();
    for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i];
    return os;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v){
    for (auto &x : v) is >> x;
    return is;
}

void in() {}
template <typename T, class... U>
void in(T &t, U &...u){
    cin >> t;
    in(u...);
}

void out() { cout << "\n"; }
template <typename T, class... U, char sep = ' '>
void out(const T &t, const U &...u){
    cout << t;
    if (sizeof...(u)) cout << sep;
    out(u...);
}

template<typename T>
void out(const vector<vector<T>> &vv){
    int s = (int)vv.size();
    for (int i = 0; i < s; i++) out(vv[i]);
}

struct IoSetup {
    IoSetup(){
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(15);
        cerr << fixed << setprecision(7);
    }
} iosetup_noya2;

} // namespace noya2
#line 1 "/Users/noya2/Desktop/Noya2_library/template/const.hpp"
namespace noya2{

const int iinf = 1'000'000'007;
const long long linf = 2'000'000'000'000'000'000LL;
const long long mod998 =  998244353;
const long long mod107 = 1000000007;
const long double pi = 3.14159265358979323;
const vector<int> dx = {0,1,0,-1,1,1,-1,-1};
const vector<int> dy = {1,0,-1,0,1,-1,-1,1};
const string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string alp = "abcdefghijklmnopqrstuvwxyz";
const string NUM = "0123456789";

void yes(){ cout << "Yes\n"; }
void no(){ cout << "No\n"; }
void YES(){ cout << "YES\n"; }
void NO(){ cout << "NO\n"; }
void yn(bool t){ t ? yes() : no(); }
void YN(bool t){ t ? YES() : NO(); }

} // namespace noya2
#line 2 "/Users/noya2/Desktop/Noya2_library/template/utils.hpp"

#line 6 "/Users/noya2/Desktop/Noya2_library/template/utils.hpp"

namespace noya2{

unsigned long long inner_binary_gcd(unsigned long long a, unsigned long long b){
    if (a == 0 || b == 0) return a + b;
    int n = __builtin_ctzll(a); a >>= n;
    int m = __builtin_ctzll(b); b >>= m;
    while (a != b) {
        int mm = __builtin_ctzll(a - b);
        bool f = a > b;
        unsigned long long c = f ? a : b;
        b = f ? b : a;
        a = (c - b) >> mm;
    }
    return a << std::min(n, m);
}

template<typename T> T gcd_fast(T a, T b){ return static_cast<T>(inner_binary_gcd(std::abs(a),std::abs(b))); }

long long sqrt_fast(long long n) {
    if (n <= 0) return 0;
    long long x = sqrt(n);
    while ((x + 1) * (x + 1) <= n) x++;
    while (x * x > n) x--;
    return x;
}

template<typename T> T floor_div(const T n, const T d) {
    assert(d != 0);
    return n / d - static_cast<T>((n ^ d) < 0 && n % d != 0);
}

template<typename T> T ceil_div(const T n, const T d) {
    assert(d != 0);
    return n / d + static_cast<T>((n ^ d) >= 0 && n % d != 0);
}

template<typename T> void uniq(std::vector<T> &v){
    std::sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
}

template <typename T, typename U> inline bool chmin(T &x, U y) { return (y < x) ? (x = y, true) : false; }

template <typename T, typename U> inline bool chmax(T &x, U y) { return (x < y) ? (x = y, true) : false; }

template<typename T> inline bool range(T l, T x, T r){ return l <= x && x < r; }

} // namespace noya2
#line 8 "/Users/noya2/Desktop/Noya2_library/template/template.hpp"

#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define repp(i,m,n) for (int i = (m); i < (int)(n); i++)
#define reb(i,n) for (int i = (int)(n-1); i >= 0; i--)
#define all(v) (v).begin(),(v).end()

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pil = pair<int,ll>;
using pli = pair<ll,int>;

namespace noya2{

/*　~ (. _________ . /)　*/

}

using namespace noya2;


#line 2 "c.cpp"

#line 2 "/Users/noya2/Desktop/Noya2_library/utility/modint.hpp"

#line 4 "/Users/noya2/Desktop/Noya2_library/utility/modint.hpp"

#line 2 "/Users/noya2/Desktop/Noya2_library/math/prime.hpp"

#line 4 "/Users/noya2/Desktop/Noya2_library/math/prime.hpp"
namespace noya2 {

constexpr long long safe_mod(long long x, long long m) {
    x %= m;
    if (x < 0) x += m;
    return x;
}

constexpr long long pow_mod_constexpr(long long x, long long n, int m) {
    if (m == 1) return 0;
    unsigned int _m = (unsigned int)(m);
    unsigned long long r = 1;
    unsigned long long y = safe_mod(x, m);
    while (n) {
        if (n & 1) r = (r * y) % _m;
        y = (y * y) % _m;
        n >>= 1;
    }
    return r;
}

constexpr bool is_prime_constexpr(int n) {
    if (n <= 1) return false;
    if (n == 2 || n == 7 || n == 61) return true;
    if (n % 2 == 0) return false;
    long long d = n - 1;
    while (d % 2 == 0) d /= 2;
    constexpr long long bases[3] = {2, 7, 61};
    for (long long a : bases) {
        long long t = d;
        long long y = pow_mod_constexpr(a, t, n);
        while (t != n - 1 && y != 1 && y != n - 1) {
            y = y * y % n;
            t <<= 1;
        }
        if (y != n - 1 && t % 2 == 0) {
            return false;
        }
    }
    return true;
}
template <int n> constexpr bool is_prime_flag = is_prime_constexpr(n);

// {gcd(a, b), a^{-1} mod b}
constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {
    a = safe_mod(a, b);
    if (a == 0) return {b, 0};
    long long s = b, t = a;
    long long m0 = 0, m1 = 1;
    while (t) {
        long long u = s / t;
        s -= t * u;
        m0 -= m1 * u; 
        auto tmp = s;
        s = t;
        t = tmp;
        tmp = m0;
        m0 = m1;
        m1 = tmp;
    }
    if (m0 < 0) m0 += b / s;
    return {s, m0};
}

constexpr int primitive_root_constexpr(int m) {
    if (m == 2) return 1;
    if (m == 167772161) return 3;
    if (m == 469762049) return 3;
    if (m == 754974721) return 11;
    if (m == 998244353) return 3;
    int divs[20] = {};
    divs[0] = 2;
    int cnt = 1;
    int x = (m - 1) / 2;
    while (x % 2 == 0) x /= 2;
    for (int i = 3; (long long)(i)*i <= x; i += 2) {
        if (x % i == 0) {
            divs[cnt++] = i;
            while (x % i == 0) {
                x /= i;
            }
        }
    }
    if (x > 1) {
        divs[cnt++] = x;
    }
    for (int g = 2;; g++) {
        bool ok = true;
        for (int i = 0; i < cnt; i++) {
            if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {
                ok = false;
                break;
            }
        }
        if (ok) return g;
    }
}
template <int m> constexpr int primitive_root_flag = primitive_root_constexpr(m);

// constexpr long long primitive_root_constexpr(long long m){
//     if (m == (1LL << 47) - (1LL << 24) + 1) return 3;
//     return primitive_root_constexpr(static_cast<int>(m));
// }

} // namespace noya2
#line 6 "/Users/noya2/Desktop/Noya2_library/utility/modint.hpp"

namespace noya2{

struct barrett {
    unsigned int _m;
    unsigned long long im;
    explicit barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}
    unsigned int umod() const { return _m; }
    unsigned int mul(unsigned int a, unsigned int b) const {
        unsigned long long z = a;
        z *= b;
        unsigned long long x = (unsigned long long)((__uint128_t(z) * im) >> 64);
        unsigned int v = (unsigned int)(z - x * _m);
        if (_m <= v) v += _m;
        return v;
    }
};

template <int m>
struct static_modint {
    using mint = static_modint;
  public:
    static constexpr int mod() { return m; }
    static mint raw(int v) {
        mint x;
        x._v = v;
        return x;
    }
    constexpr static_modint() : _v(0) {}
    template<std::signed_integral T>
    constexpr static_modint(T v){
        long long x = (long long)(v % (long long)(umod()));
        if (x < 0) x += umod();
        _v = (unsigned int)(x);
    }
    template<std::unsigned_integral T>
    constexpr static_modint(T v){
        _v = (unsigned int)(v % umod());
    }
    constexpr unsigned int val() const { return _v; }
    mint& operator++() {
        _v++;
        if (_v == umod()) _v = 0;
        return *this;
    }
    mint& operator--() {
        if (_v == 0) _v = umod();
        _v--;
        return *this;
    }
    mint operator++(int) {
        mint result = *this;
        ++*this;
        return result;
    }
    mint operator--(int) {
        mint result = *this;
        --*this;
        return result;
    }
    constexpr mint& operator+=(const mint& rhs) {
        _v += rhs._v;
        if (_v >= umod()) _v -= umod();
        return *this;
    }
    constexpr mint& operator-=(const mint& rhs) {
        _v -= rhs._v;
        if (_v >= umod()) _v += umod();
        return *this;
    }
    constexpr mint& operator*=(const mint& rhs) {
        unsigned long long z = _v;
        z *= rhs._v;
        _v = (unsigned int)(z % umod());
        return *this;
    }
    constexpr mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
    constexpr mint operator+() const { return *this; }
    constexpr mint operator-() const { return mint() - *this; }
    constexpr mint pow(long long n) const {
        assert(0 <= n);
        mint x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    constexpr mint inv() const {
        if (prime) {
            assert(_v);
            return pow(umod() - 2);
        } else {
            auto eg = inv_gcd(_v, m);
            assert(eg.first == 1);
            return eg.second;
        }
    }
    friend constexpr mint operator+(const mint& lhs, const mint& rhs) {
        return mint(lhs) += rhs;
    }
    friend constexpr mint operator-(const mint& lhs, const mint& rhs) {
        return mint(lhs) -= rhs;
    }
    friend constexpr mint operator*(const mint& lhs, const mint& rhs) {
        return mint(lhs) *= rhs;
    }
    friend constexpr mint operator/(const mint& lhs, const mint& rhs) {
        return mint(lhs) /= rhs;
    }
    friend constexpr bool operator==(const mint& lhs, const mint& rhs) {
        return lhs._v == rhs._v;
    }
    friend constexpr bool operator!=(const mint& lhs, const mint& rhs) {
        return lhs._v != rhs._v;
    }
    friend std::ostream &operator<<(std::ostream &os, const mint& p) {
        return os << p.val();
    }
    friend std::istream &operator>>(std::istream &is, mint &a) {
        long long t; is >> t;
        a = mint(t);
        return (is);
    }

  private:
    unsigned int _v;
    static constexpr unsigned int umod() { return m; }
    static constexpr bool prime = is_prime_flag<m>;
};


template <int id> struct dynamic_modint {
    using mint = dynamic_modint;
  public:
    static int mod() { return (int)(bt.umod()); }
    static void set_mod(int m) {
        assert(1 <= m);
        bt = barrett(m);
    }
    static mint raw(int v) {
        mint x;
        x._v = v;
        return x;
    }

    dynamic_modint() : _v(0) {}
    template<std::signed_integral T>
    dynamic_modint(T v){
        long long x = (long long)(v % (long long)(umod()));
        if (x < 0) x += umod();
        _v = (unsigned int)(x);
    }
    template<std::unsigned_integral T>
    dynamic_modint(T v){
        _v = (unsigned int)(v % umod());
    }
    unsigned int val() const { return _v; }
    mint& operator++() {
        _v++;
        if (_v == umod()) _v = 0;
        return *this;
    }
    mint& operator--() {
        if (_v == 0) _v = umod();
        _v--;
        return *this;
    }
    mint operator++(int) {
        mint result = *this;
        ++*this;
        return result;
    }
    mint operator--(int) {
        mint result = *this;
        --*this;
        return result;
    }
    mint& operator+=(const mint& rhs) {
        _v += rhs._v;
        if (_v >= umod()) _v -= umod();
        return *this;
    }
    mint& operator-=(const mint& rhs) {
        _v += mod() - rhs._v;
        if (_v >= umod()) _v -= umod();
        return *this;
    }
    mint& operator*=(const mint& rhs) {
        _v = bt.mul(_v, rhs._v);
        return *this;
    }
    mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
    mint operator+() const { return *this; }
    mint operator-() const { return mint() - *this; }
    mint pow(long long n) const {
        assert(0 <= n);
        mint x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    mint inv() const {
        auto eg = noya2::inv_gcd(_v, mod());
        assert(eg.first == 1);
        return eg.second;
    }
    friend mint operator+(const mint& lhs, const mint& rhs) {
        return mint(lhs) += rhs;
    }
    friend mint operator-(const mint& lhs, const mint& rhs) {
        return mint(lhs) -= rhs;
    }
    friend mint operator*(const mint& lhs, const mint& rhs) {
        return mint(lhs) *= rhs;
    }
    friend mint operator/(const mint& lhs, const mint& rhs) {
        return mint(lhs) /= rhs;
    }
    friend bool operator==(const mint& lhs, const mint& rhs) {
        return lhs._v == rhs._v;
    }
    friend bool operator!=(const mint& lhs, const mint& rhs) {
        return lhs._v != rhs._v;
    }
    friend std::ostream &operator<<(std::ostream &os, const mint& p) {
        return os << p.val();
    }
    friend std::istream &operator>>(std::istream &is, mint &a) {
        long long t; is >> t;
        a = mint(t);
        return (is);
    }

  private:
    unsigned int _v;
    static barrett bt;
    static unsigned int umod() { return bt.umod(); }
};
template <int id> noya2::barrett dynamic_modint<id>::bt(998244353);

using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;
using modint = dynamic_modint<-1>;

template<typename T>
concept Modint = requires (T &a){
    T::mod();
    a.inv();
    a.val();
    a.pow(declval<int>());
};

} // namespace noya2
#line 4 "c.cpp"
using mint = modint998244353;
#line 2 "/Users/noya2/Desktop/Noya2_library/math/binomial.hpp"

#line 4 "/Users/noya2/Desktop/Noya2_library/math/binomial.hpp"
namespace noya2 {

template<typename mint>
struct binomial {
    binomial(int len = 300000){ extend(len); }
    static mint fact(int n){
        if (n < 0) return 0;
        while (n >= (int)_fact.size()) extend();
        return _fact[n];
    }
    static mint ifact(int n){
        if (n < 0) return 0;
        while (n >= (int)_fact.size()) extend();
        return _ifact[n];
    }
    static mint inv(int n){
        return ifact(n) * fact(n-1);
    }
    static mint C(int n, int r){
        if (!(0 <= r && r <= n)) return 0;
        return fact(n) * ifact(r) * ifact(n-r);
    }
    static mint P(int n, int r){
        if (!(0 <= r && r <= n)) return 0;
        return fact(n) * ifact(n-r);
    }
    static mint catalan(int n){
        return C(n * 2, n) * inv(n + 1);
    }
    inline mint operator()(int n, int r) { return C(n, r); }
    template<class... Cnts>
    static mint M(const Cnts&... cnts){
        return multinomial(0,1,cnts...);
    }
    static void initialize(int len = 2){
        _fact.clear();
        _ifact.clear();
        _fact = {1,1};
        _ifact = {1,1};
        extend(len);
    }
  private:
    static mint multinomial(const int& sum, const mint& div_prod){
        if (sum < 0) return 0;
        return fact(sum) * div_prod;
    }
    template<class... Tail>
    static mint multinomial(const int& sum, const mint& div_prod, const int& n1, const Tail&... tail){
        if (n1 < 0) return 0;
        return multinomial(sum+n1,div_prod*ifact(n1),tail...);
    }
    static std::vector<mint> _fact, _ifact;
    static void extend(int len = -1){
        int siz = _fact.size();
        if (siz == 0){
            _fact = {1,1};
            _ifact = {1,1};
            siz = _fact.size();
        }
        if (len == -1) len = siz * 2;
        len = (int)min<long long>(len, mint::mod() - 1);
        if (len < siz) return ;
        _fact.resize(len+1), _ifact.resize(len+1);
        for (int i = siz; i <= len; i++) _fact[i] = _fact[i-1] * i;
        assert(_fact[len].val() != 0);
        _ifact[len] = _fact[len].inv();
        for (int i = len; i > siz; i--) _ifact[i-1] = _ifact[i] * i;
    }
};
template<typename mint> std::vector<mint> noya2::binomial<mint>::_fact = {1,1};
template<typename mint> std::vector<mint> noya2::binomial<mint>::_ifact = {1,1};

} // namespace noya2
#line 6 "c.cpp"
binomial<mint> bnm;
#line 2 "/Users/noya2/Desktop/Noya2_library/fps998244353/fps998244353.hpp"

#line 4 "/Users/noya2/Desktop/Noya2_library/fps998244353/fps998244353.hpp"

#line 2 "/Users/noya2/Desktop/Noya2_library/fps998244353/ntt998244353.hpp"

#line 2 "/Users/noya2/Desktop/Noya2_library/fps998244353/modint998244353.hpp"

#line 4 "/Users/noya2/Desktop/Noya2_library/fps998244353/modint998244353.hpp"

#line 6 "/Users/noya2/Desktop/Noya2_library/fps998244353/modint998244353.hpp"

namespace noya2 {

template <>
struct static_modint<998244353> {
    using mint = static_modint;
  public:
    static constexpr int mod() { return 998244353; }
    static mint raw(int v) {
        mint x;
        x._v = v;
        return x;
    }
    constexpr static_modint() : _v(0) {}
    template<std::signed_integral T>
    constexpr static_modint(T v){
        long long x = (long long)(v % (long long)(umod()));
        if (x < 0) x += umod();
        _v = (unsigned int)(x);
    }
    template<std::unsigned_integral T>
    constexpr static_modint(T v){
        _v = (unsigned int)(v % umod());
    }
    constexpr unsigned int val() const { return _v; }
    mint& operator++() {
        _v++;
        if (_v == umod()) _v = 0;
        return *this;
    }
    mint& operator--() {
        if (_v == 0) _v = umod();
        _v--;
        return *this;
    }
    mint operator++(int) {
        mint result = *this;
        ++*this;
        return result;
    }
    mint operator--(int) {
        mint result = *this;
        --*this;
        return result;
    }
    constexpr mint& operator+=(const mint& rhs) {
        _v += rhs._v;
        if (_v >= umod()) _v -= umod();
        return *this;
    }
    constexpr mint& operator-=(const mint& rhs) {
        _v -= rhs._v;
        if (_v >= umod()) _v += umod();
        return *this;
    }
    constexpr mint& operator*=(const mint& rhs) {
        unsigned long long z = _v;
        z *= rhs._v;
        _v = (unsigned int)(z % umod());
        return *this;
    }
    constexpr mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
    constexpr mint operator+() const { return *this; }
    constexpr mint operator-() const { return mint() - *this; }
    constexpr mint pow(long long n) const {
        assert(0 <= n);
        mint x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    constexpr mint inv() const {
        assert(_v);
        return pow(umod() - 2);
    }
    friend constexpr mint operator+(const mint& lhs, const mint& rhs) {
        return mint(lhs) += rhs;
    }
    friend constexpr mint operator-(const mint& lhs, const mint& rhs) {
        return mint(lhs) -= rhs;
    }
    friend constexpr mint operator*(const mint& lhs, const mint& rhs) {
        return mint(lhs) *= rhs;
    }
    friend constexpr mint operator/(const mint& lhs, const mint& rhs) {
        return mint(lhs) /= rhs;
    }
    friend constexpr bool operator==(const mint& lhs, const mint& rhs) {
        return lhs._v == rhs._v;
    }
    friend constexpr bool operator!=(const mint& lhs, const mint& rhs) {
        return lhs._v != rhs._v;
    }
    friend std::ostream &operator<<(std::ostream &os, const mint& p) {
        return os << p.val();
    }
    friend std::istream &operator>>(std::istream &is, mint &a) {
        long long t; is >> t;
        a = mint(t);
        return (is);
    }

    unsigned int _v;
    static constexpr int primitive_root_constexpr_v = 3;
  private:
    static constexpr unsigned int umod() { return 998244353u; }
    static constexpr bool prime = true;
};

} // namespace noya2
#line 4 "/Users/noya2/Desktop/Noya2_library/fps998244353/ntt998244353.hpp"

#line 7 "/Users/noya2/Desktop/Noya2_library/fps998244353/ntt998244353.hpp"

namespace noya2 {

namespace internal {

constexpr int FFT_MAX = 23;
constexpr unsigned FFT_ROOTS[FFT_MAX + 1] = {1U, 998244352U, 911660635U, 372528824U, 929031873U, 452798380U, 922799308U, 781712469U, 476477967U, 166035806U, 258648936U, 584193783U, 63912897U, 350007156U, 666702199U, 968855178U, 629671588U, 24514907U, 996173970U, 363395222U, 565042129U, 733596141U, 267099868U, 15311432U};
constexpr unsigned INV_FFT_ROOTS[FFT_MAX + 1] = {1U, 998244352U, 86583718U, 509520358U, 337190230U, 87557064U, 609441965U, 135236158U, 304459705U, 685443576U, 381598368U, 335559352U, 129292727U, 358024708U, 814576206U, 708402881U, 283043518U, 3707709U, 121392023U, 704923114U, 950391366U, 428961804U, 382752275U, 469870224U};
constexpr unsigned FFT_RATIOS[FFT_MAX] = {911660635U, 509520358U, 369330050U, 332049552U, 983190778U, 123842337U, 238493703U, 975955924U, 603855026U, 856644456U, 131300601U, 842657263U, 730768835U, 942482514U, 806263778U, 151565301U, 510815449U, 503497456U, 743006876U, 741047443U, 56250497U, 867605899U};
constexpr unsigned INV_FFT_RATIOS[FFT_MAX] = {86583718U, 372528824U, 373294451U, 645684063U, 112220581U, 692852209U, 155456985U, 797128860U, 90816748U, 860285882U, 927414960U, 354738543U, 109331171U, 293255632U, 535113200U, 308540755U, 121186627U, 608385704U, 438932459U, 359477183U, 824071951U, 103369235U};

} // namespace noya2::internal

struct ntt998244353 {
    using mint = modint998244353;
    static constexpr unsigned MO = modint998244353::mod();
    static constexpr unsigned MO2 = MO * 2;
    static void ntt(mint *as, int n){
        int m = n;
        if (m >>= 1){
            for (int i = 0; i < m; i++){
                const unsigned x = as[i + m]._v;
                as[i + m]._v = as[i]._v + MO - x;
                as[i]._v += x;
            }
        }
        if (m >>= 1){
            mint prod = 1;
            for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)){
                for (int i = i0; i < i0 + m; i++){
                    const unsigned x = (prod * as[i + m])._v;
                    as[i + m]._v = as[i]._v + MO - x;
                    as[i]._v += x;
                }
                prod *= mint::raw(internal::FFT_RATIOS[__builtin_ctz(++h)]);
            }
        }
        for (; m; ){
            if (m >>= 1){
                mint prod = 1;
                for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)){
                    for (int i = i0; i < i0 + m; i++){
                        const unsigned x = (prod * as[i + m])._v;
                        as[i + m]._v = as[i]._v + MO - x;
                        as[i]._v += x;
                    }
                    prod *= mint::raw(internal::FFT_RATIOS[__builtin_ctz(++h)]);
                }
            }
            if (m >>= 1){
                mint prod = 1;
                for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)){
                    for (int i = i0; i < i0 + m; i++){
                        const unsigned x = (prod * as[i + m])._v;
                        as[i]._v = (as[i]._v >= MO2 ? as[i]._v - MO2 : as[i]._v);
                        as[i + m]._v = as[i]._v + MO - x;
                        as[i]._v += x;
                    }
                    prod *= mint::raw(internal::FFT_RATIOS[__builtin_ctz(++h)]);
                }
            }
        }
        for (int i = 0; i < n; i++){
            as[i]._v = (as[i]._v >= MO2 ? as[i]._v - MO2 : as[i]._v);
            as[i]._v = (as[i]._v >= MO ? as[i]._v - MO : as[i]._v);
        }
    }
    static void intt(mint *as, int n){
        int m = 1;
        if (m < (n >> 1)){
            mint prod = 1;
            for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)){
                for (int i = i0; i < i0 + m; i++){
                    const unsigned long long y = as[i]._v + MO - as[i + m]._v;
                    as[i]._v += as[i + m]._v;
                    as[i + m]._v = prod._v * y % MO;
                }
                prod *= mint::raw(internal::INV_FFT_RATIOS[__builtin_ctz(++h)]);
            }
            m <<= 1;
        }
        for (; m < (n >> 1); m <<= 1){
            mint prod = 1;
            for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)){
                for (int i = i0; i < i0 + (m >> 1); i++){
                    const unsigned long long y = as[i]._v + MO2 - as[i + m]._v;
                    as[i]._v += as[i + m]._v;
                    as[i]._v = (as[i]._v >= MO2 ? as[i]._v - MO2 : as[i]._v);
                    as[i + m]._v = prod._v * y % MO;
                }
                for (int i = i0 + (m >> 1); i < i0 + m; i++){
                    const unsigned long long y = as[i]._v + MO - as[i + m]._v;
                    as[i]._v += as[i + m]._v;
                    as[i + m]._v = prod._v * y % MO;
                }
                prod *= mint::raw(internal::INV_FFT_RATIOS[__builtin_ctz(++h)]);
            }
        }
        if (m < n){
            for (int i = 0; i < m; i++){
                const unsigned y = as[i]._v + MO2 - as[i + m]._v;
                as[i]._v += as[i + m]._v;
                as[i + m]._v = y;
            }
        }
        for (int i = 0; i < n; i++){
            as[i]._v = (as[i]._v >= MO2 ? as[i]._v - MO2 : as[i]._v);
            as[i]._v = (as[i]._v >= MO ? as[i]._v - MO : as[i]._v);
        }
    }
    static void ntt(std::vector<mint> &as){
        ntt(as.data(), as.size());
    }
    static void intt(std::vector<mint> &as){
        intt(as.data(), as.size());
    }
    static void intt_div(std::vector<mint> &as){
        intt(as);
        int n = as.size();
        const mint inv_n = mint::raw(n).inv();
        for (int i = 0; i < n; i++){
            as[i] *= inv_n;
        }
    }
    static std::vector<mint> multiply(std::vector<mint> as, std::vector<mint> bs){
        if (as.empty() || bs.empty()) return {};
        const int len = as.size() + bs.size() - 1u;
        if (std::min(as.size(), bs.size()) <= 40u){
            std::vector<mint> s(len);
            for (int i = 0; i < (int)(as.size()); i++){
                for (int j = 0; j < (int)(bs.size()); j++){
                    s[i + j] += as[i] * bs[j];
                }
            }
            return s;
        }
        int n = 1;
        for (; n < len; n <<= 1) {}
        if (as.size() == bs.size() && as == bs){
            as.resize(n);
            ntt(as);
            for (int i = 0; i < n; i++){
                as[i] *= as[i];
            }
        }
        else {
            as.resize(n);
            ntt(as);
            bs.resize(n);
            ntt(bs);
            for (int i = 0; i < n; i++){
                as[i] *= bs[i];
            }
        }
        intt_div(as);
        as.resize(len);
        return as;
    }
    static void ntt_doubling(std::vector<mint> &as){
        auto bs = as;
        intt(bs);
        mint e = mint::raw(internal::FFT_ROOTS[std::countr_zero(as.size()) + 1]);
        mint iv = mint::raw(as.size()).inv();
        for (auto &x : bs){
            x *= iv;
            iv *= e;
        }
        ntt(bs);
        as.insert(as.end(), bs.begin(), bs.end());
    }
    static void ntt_pick_parity(std::vector<mint> &f, int odd){
        int n = f.size() / 2;
        mint i2 = mint::raw((mint::mod() + 1) >> 1);
        if (odd == 0){
            for (int i = 0; i < n; i++){
                f[i] = (f[i * 2] + f[i * 2 + 1]) * i2;
            }
            f.resize(n);
            return ;
        }
        mint ie = mint::raw(internal::INV_FFT_ROOTS[std::countr_zero(f.size())]);
        std::vector<mint> es = {i2};
        while ((int)(es.size()) != n){
            std::vector<mint> nes(es.size() * 2u);
            for (int i = 0; i < (int)(es.size()); i++){
                nes[i * 2 + 0] = es[i];
                nes[i * 2 + 1] = es[i] * ie;
            }
            ie *= ie;
            std::swap(es, nes);
        }
        for (int i = 0; i < n; i++){
            f[i] = (f[i * 2] - f[i * 2 + 1]) * es[i];
        }
        f.resize(n);
    }
};

} // namespace noya2
#line 7 "/Users/noya2/Desktop/Noya2_library/fps998244353/fps998244353.hpp"

namespace noya2 {

// Formal Power Series for modint998244353
struct fps998244353 : std::vector<modint998244353> {
    using mint = modint998244353;
    using std::vector<mint>::vector;
    using std::vector<mint>::operator=;
    using fps = fps998244353;
    static inline binomial<mint> bnm;

    fps998244353 (const std::vector<mint> &init){
        (*this) = init;
    }

    void shrink(){
        while(!(this->empty()) && this->back().val() == 0){
            this->pop_back();
        }
    }

    fps &operator*= (const mint &r){
        for (auto &x : *this) x *= r;
        return *this;
    }
    fps &operator/= (const mint &r){
        (*this) *= r.inv();
        return *this;
    }

    fps &operator<<= (const int &d){
        this->insert(this->begin(), d, mint(0));
        return *this;
    }
    fps &operator>>= (const int &d){
        if ((int)(this->size()) <= d) this->clear();
        else this->erase(this->begin(),this->begin() + d);
        return *this;
    }

    fps &operator+= (const fps &r){
        if (this->size() < r.size()) this->resize(r.size());
        for (int i = 0; auto x : r){
            (*this)[i++] += x;
        }
        return *this;
    }
    fps &operator-= (const fps &r){
        if (this->size() < r.size()) this->resize(r.size());
        for (int i = 0; auto x : r){
            (*this)[i++] -= x;
        }
        return *this;
    }
    fps &operator*= (const fps &r){
        if (this->empty() || r.empty()){
            this->clear();
            return *this;
        }
        (*this) = ntt998244353::multiply(*this, r);
        return *this;
    }

    fps operator* (const mint &r) const { return fps(*this) *= r; }
    fps operator/ (const mint &r) const { return fps(*this) /= r; }
    fps operator<< (const int &d) const { return fps(*this) <<= d; }
    fps operator>> (const int &d) const { return fps(*this) >>= d; }

    fps operator+ (const fps &r) const { return fps(*this) += r; }
    fps operator- (const fps &r) const { return fps(*this) -= r; }
    fps operator* (const fps &r) const { return fps(*this) *= r; }

    fps operator+ () const { return *this; }
    fps operator- () const {
        fps ret(*this);
        for (auto &x : ret) x = -x;
        return ret;
    }

    mint eval(const mint &x) const {
        mint res(0), w(1);
        for (auto a : *this){
            res += a * w;
            w *= x;
        }
        return res;
    }

    [[nodiscard("Do not change but return changed object.")]]
    fps pre(std::size_t sz) const {
        fps ret(this->begin(), this->begin() + std::min(this->size(), sz));
        if (ret.size() < sz) ret.resize(sz);
        return ret;
    }
    [[nodiscard("Do not change but return changed object.")]]
    fps rev() const {
        fps ret(*this);
        std::reverse(ret.begin(), ret.end());
        return ret;
    }
    [[nodiscard("Do not change but return changed object.")]]
    fps diff() const {
        if (this->empty()){
            return fps();
        }
        fps ret(this->begin() + 1, this->end());
        for (int i = 1; auto &x : ret){
            x *= i++;
        }
        return ret;
    }
    [[nodiscard("Do not change but return changed object.")]]
    fps integral() const {
        if (this->empty()){
            return fps();
        }
        fps ret(1, mint(0));
        ret.insert(ret.end(), this->begin(), this->end());
        for (int i = 0; auto &x : ret){
            x *= bnm.inv(i++); // inv(0) = 0
        }
        return ret;
    }
    [[nodiscard("Do not change but return changed object.")]]
    fps inv(int d = -1) const {
        const int n = this->size();
        if (d == -1) d = n;
        fps res = {(*this)[0].inv()};
        for (int siz = 1; siz < d; siz <<= 1){
            fps f(this->begin(),this->begin()+min(n,siz*2)), g(res);
            f.resize(siz*2), g.resize(siz*2);
            f.ntt(), g.ntt();
            for (int i = 0; i < siz*2; i++) f[i] *= g[i];
            f.intt();
            f.erase(f.begin(),f.begin()+siz);
            f.resize(siz*2);
            f.ntt();
            for (int i = 0; i < siz*2; i++) f[i] *= g[i];
            f.intt();
            mint siz2_inv = mint(siz*2).inv(); siz2_inv *= -siz2_inv;
            for (int i = 0; i < siz; i++) f[i] *= siz2_inv;
            res.insert(res.end(),f.begin(),f.begin()+siz);
        }
        res.resize(d);
        return res;
    }
    [[nodiscard("Do not change but return changed object.")]]
    fps log(int d = -1) const {
        assert(this->empty() == false && (*this)[0].val() == 1u);
        if (d == -1) d = this->size();
        return (this->diff() * this->inv(d)).pre(d - 1).integral();
    }
    [[nodiscard("Do not change but return changed object.")]]
    fps exp(int d = -1) const {
        const int n = this->size();
        if (d == -1) d = n;
        assert(n == 0 || (*this)[0].val() == 0u);
        if (n <= 1){
            fps ret(1,1);
            ret.resize(d);
            return ret;
        }
        // n >= 2
        fps f = {mint(1), (*this)[1]}, ret = f;
        for (int sz = 2; sz < d; sz <<= 1){
            f.insert(f.end(), this->begin()+std::min(n,sz), this->begin()+std::min(n,sz*2));
            f.resize(sz*2);
            ret *= f - ret.log(sz*2);
            ret.resize(sz*2);
        }
        ret.resize(d);
        return ret;
    }
    [[nodiscard("Do not change but return changed object.")]]
    fps pow(long long k, int d = -1) const {
        const int n = this->size();
        if (d == -1) d = n;
        if (k == 0){
            fps ret(d, mint(0));
            if (d >= 1) ret[0] = 1;
            return ret;
        }
        // Find left-most nonzero term.
        for (int i = 0; i < n; i++){
            if ((*this)[i].val() != 0u){
                mint iv = (*this)[i].inv();
                fps ret = ((((*this) * iv) >> i).log(d) * mint(k)).exp(d);
                ret *= (*this)[i].pow(k);
                ret = (ret << (i * k)).pre(d);
                return ret;
            }
            if ((i + 1) * k >= d) break;
        }
        return fps(d, mint(0));
    }

    void ntt(){
        ntt998244353::ntt(*this);
    }
    // NOT /= len
    void intt(){
        ntt998244353::intt(*this);
    }
    // already /= len
    void intt_div(){
        ntt998244353::intt_div(*this);
    }
    //  input : ntt( f[0, 2^n) )
    // output : ntt( f[0, 2^n) ++ zero_padding[0, 2^n) )
    void ntt_doubling(){
        ntt998244353::ntt_doubling(*this);
    }
    //  input : ntt( f[0, 2^n) )
    // output : ntt( g[0, 2^{n-1}) ), g[i] = f[i * 2 + odd]
    void ntt_pick_parity(int odd){
        ntt998244353::ntt_pick_parity(*this, odd);
    }
    fps quotient(fps r) const {
        r.shrink();
        const int n = this->size(), m = r.size();
        if (n < m){
            return fps();
        }
        fps quo(*this);
        const int sz = n - m + 1;
        std::reverse(quo.begin(), quo.end());
        std::reverse(r.begin(), r.end());
        quo.resize(sz);
        quo *= r.inv(sz);
        quo.resize(sz);
        std::reverse(quo.begin(), quo.end());
        return quo;
    }
    fps remainder(fps r) const {
        r.shrink();
        const int n = this->size(), m = r.size();
        if (n < m){
            return fps(*this);
        }
        fps rem(*this);
        rem -= quotient(r) * r;
        rem.resize(m-1);
        rem.shrink();
        return rem;
    }
    std::pair<fps,fps> remquo(fps r) const {
        r.shrink();
        fps quo = quotient(r);
        fps rem(*this);
        rem -= quo * r;
        rem.shrink();
        return {rem, quo};
    }
};

} // namespace noya2
#line 8 "c.cpp"
using fps = fps998244353;
#line 2 "/Users/noya2/Desktop/Noya2_library/fps998244353/multipoint_evaluation.hpp"

#line 4 "/Users/noya2/Desktop/Noya2_library/fps998244353/multipoint_evaluation.hpp"

namespace noya2 {

std::vector<modint998244353> multipoint_evaluation(fps998244353 f, const std::vector<modint998244353> &xs){
    const int n = xs.size();
    int sz = 1;
    while(sz < n) sz <<= 1;
    std::vector<fps998244353> g(sz+sz,{1});
    for(int i = 0; i < n; i++) g[i+sz] = {-xs[i],1};
    for(int i = sz; i-->1;) g[i] = g[i<<1] * g[i<<1|1];
    g[1] = f.remainder(g[1]);
    for(int i = 2; i < sz+n; i++) g[i] = g[i>>1].remainder(g[i]);
    std::vector<modint998244353> res(n);
    for(int i = 0; i < n; i++) res[i] = (g[i+sz].empty() ? modint998244353() : g[i+sz][0]);
    return res;
}

std::vector<modint998244353> multipoint_evaluation_geo(const fps998244353 &f, modint998244353 a, modint998244353 r, int m){
    using mint = modint998244353;
    int n = f.size();
    if (r.val() == 0){
        std::vector<mint> ans(m);
        repp(i,1,m) ans[i] = f[0];
        ans[0] = f.eval(a);
        return ans;
    }
    fps998244353 p(n);
    mint aprd = 1;
    mint ir = r.inv();
    mint irpp = 1, irp = 1;
    for (int i = 0; i < n; i++){
        p[n-1-i] = aprd * f[i] * irpp;
        irpp *= irp;
        irp *= ir;
        aprd *= a;
    }
    fps998244353 q(n+m-1);
    mint rpp = 1, rp = 1;
    for (int i = 0; i < n+m-1; i++){
        q[i] = rpp;
        rpp *= rp;
        rp *= r;
    }
    p *= q;
    std::vector<mint> ans(m);
    irpp = 1, irp = 1;
    for (int i = 0; i < m; i++){
        ans[i] = p[n-1+i] * irpp;
        irpp *= irp;
        irp *= ir;
    }
    return ans;
}

} // namespace noya2
#line 10 "c.cpp"

// [x^n](1/(1-x))^k
mint h(int n, int k){
    if (k == 0){
        return int(n == 0);
    }
    return bnm(n+k-1,k-1);
}

// [x^n](exp(x))^k
mint h2(int n, int k){
    // return fps{0,k}.exp(n+1)[n];
    return mint(k).pow(n) * bnm.ifact(n);
}

void jikken1(){
    int n; in(n);
    mint ans = 0;
    repp(k,1,n+1) rep(p,n+1){
        mint sum = 0;
        rep(i,k+1){
            sum += bnm(k,i) * h2(p,i) * (i % 2 == 0 ? 1 : -1) * h2(n-p,n-i);
        }
        ans += sum * mint(n-p).pow(n);
    }
    ans *= bnm.fact(n);
    out(ans);
}

void jikken2(){
    int n; in(n);
    mint ans = 0;
    rep(p,n+1) rep(i,n+1){
        ans += mint(n-p).pow(n) * (i % 2 == 0 ? 1 : -1) * h2(p,i) * h2(n-p,n-i) * bnm(n+1,i+1);
    }
    ans *= bnm.fact(n);
    ans -= mint(n).pow(n*2);
    out(ans);
}

namespace Forested {
#ifndef LOCAL
#define FAST_IO
#endif

#define INT128

// ============
#line 59 "c.cpp"
#define OVERRIDE(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)
#define REP3(i, m, n) for (i32 i = (i32)(m); i < (i32)(n); ++i)
#define REP(...) OVERRIDE(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define PER2(i, n) for (i32 i = (i32)(n)-1; i >= 0; --i)
#define PER3(i, m, n) for (i32 i = (i32)(n)-1; i >= (i32)(m); --i)
#define PER(...) OVERRIDE(__VA_ARGS__, PER3, PER2)(__VA_ARGS__)
#define ALL(x) begin(x), end(x)
#define LEN(x) (i32)(x.size())
using namespace std;
using u32 = unsigned int;
using u64 = unsigned long long;
using i32 = signed int;
using i64 = signed long long;
using f64 = double;
using f80 = long double;
using pi = pair<i32, i32>;
using pl = pair<i64, i64>;
template <typename T>
using V = vector<T>;
template <typename T>
using VV = V<V<T>>;
template <typename T>
using VVV = V<V<V<T>>>;
template <typename T>
using VVVV = V<V<V<V<T>>>>;
template <typename T>
using PQR = priority_queue<T, V<T>, greater<T>>;
template <typename T>
bool chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}
template <typename T>
bool chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}
template <typename T>
i32 lob(const V<T> &arr, const T &v) {
    return (i32)(lower_bound(ALL(arr), v) - arr.begin());
}
template <typename T>
i32 upb(const V<T> &arr, const T &v) {
    return (i32)(upper_bound(ALL(arr), v) - arr.begin());
}
template <typename T>
V<i32> argsort(const V<T> &arr) {
    V<i32> ret(arr.size());
    iota(ALL(ret), 0);
    sort(ALL(ret), [&](i32 i, i32 j) -> bool {
        if (arr[i] == arr[j]) {
            return i < j;
        } else {
            return arr[i] < arr[j];
        }
    });
    return ret;
}
#ifdef INT128
using u128 = __uint128_t;
using i128 = __int128_t;
#endif
[[maybe_unused]] constexpr i32 INF = 1000000100;
[[maybe_unused]] constexpr i64 INF64 = 3000000000000000100;
struct SetUpIO {
    SetUpIO() {
#ifdef FAST_IO
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
#endif
        cout << fixed << setprecision(15);
    }
} set_up_io;
void scan(char &x) { cin >> x; }
void scan(u32 &x) { cin >> x; }
void scan(u64 &x) { cin >> x; }
void scan(i32 &x) { cin >> x; }
void scan(i64 &x) { cin >> x; }
void scan(f64 &x) { cin >> x; }
void scan(string &x) { cin >> x; }
template <typename T>
void scan(V<T> &x) {
    for (T &ele : x) {
        scan(ele);
    }
}
void read() {}
template <typename Head, typename... Tail>
void read(Head &head, Tail &...tail) {
    scan(head);
    read(tail...);
}
#define CHAR(...)     \
    char __VA_ARGS__; \
    read(__VA_ARGS__);
#define U32(...)     \
    u32 __VA_ARGS__; \
    read(__VA_ARGS__);
#define U64(...)     \
    u64 __VA_ARGS__; \
    read(__VA_ARGS__);
#define I32(...)     \
    i32 __VA_ARGS__; \
    read(__VA_ARGS__);
#define I64(...)     \
    i64 __VA_ARGS__; \
    read(__VA_ARGS__);
#define F64(...)     \
    f64 __VA_ARGS__; \
    read(__VA_ARGS__);
#define STR(...)        \
    string __VA_ARGS__; \
    read(__VA_ARGS__);
#define VEC(type, name, size) \
    V<type> name(size);       \
    read(name);
#define VVEC(type, name, size1, size2)    \
    VV<type> name(size1, V<type>(size2)); \
    read(name);
// ============

#ifdef DEBUGF
#else
#define DBG(...) (void)0
#endif

// ============
#line 194 "c.cpp"
// ============
#line 197 "c.cpp"
// ============

#line 201 "c.cpp"
#include <type_traits>
// ============

#line 205 "c.cpp"

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);
    }
}

template <typename M>
std::vector<M> convolve_square_fft(std::vector<M> a) {
    int n = (int)2 * a.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() * a.back();
        m /= 2;
        while ((int)a.size() > m) {
            a[(int)a.size() - 1 - m] += a.back();
            a.pop_back();
        }
    }
    a.resize(m);
    fft(a);
    for (int i = 0; i < m; ++i) {
        a[i] *= a[i];
    }
    ifft(a);
    a.resize(n);
    if (shr) {
        a[0] -= last;
        a[n - 1] = last;
    }
    return a;
}

template <typename M>
std::vector<M> convolve_square(const std::vector<M> &a) {
    if (a.empty()) {
        return std::vector<M>(0);
    }
    if ((int)a.size() <= 60) {
        return convolve_naive(a, a);
    } else {
        return convolve_square_fft(a);
    }
}

template <typename M>
void transposed_fft(M *a, int n) {
    ifft(a, n);
    std::reverse(a + 1, a + n);
    M c(n);
    for (int i = 0; i < n; ++i) {
        a[i] *= c;
    }
}
template <typename M>
void transposed_fft(std::vector<M> &a) {
    transposed_fft(a.data(), (int)a.size());
}

template <typename M>
void transposed_ifft(M *a, int n) {
    static constexpr FFTRoot<M::get_mod()> roots;
    std::reverse(a + 1, a + n);
    fft(a, n);
    M c = roots.inv2[__builtin_ctz(n)];
    for (int i = 0; i < n; ++i) {
        a[i] *= c;
    }
}
template <typename M>
void transposed_ifft(std::vector<M> &a) {
    transposed_ifft(a.data(), (int)a.size());
}
// ============
// 10 FFT(n)
template <typename T>
std::vector<T> fps_inv(const std::vector<T> &f, int len = -1) {
    if (len == -1) {
        len = (int)f.size();
    }
    assert(!f.empty() && f[0] != T(0) && len >= 0);
    std::vector<T> g(1, T(1) / f[0]);
    while ((int)g.size() < len) {
        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(len);
    return g;
}
// ============
// ============
#line 790 "c.cpp"
// ============
// ============

// a.size() <= b.size()
template <typename M>
std::vector<M> middle_product(std::vector<M> a, std::vector<M> b) {
    int n = (int)a.size();
    int m = (int)b.size();
    assert(n <= m);
    std::reverse(a.begin(), a.end());
    int l = 1;
    while (l < m) {
        l *= 2;
    }
    a.resize(l, M());
    b.resize(l, M());
    fft(a);
    fft(b);
    for (int i = 0; i < l; ++i) {
        b[i] *= a[i];
    }
    ifft(b);
    return std::vector<M>(b.begin() + (n - 1), b.begin() + m);
}
// ============

i32 ceil_log2(i32 n) {
    i32 k = 0;
    while ((1 << k) < n) {
        ++k;
    }
    return k;
}

using M = ModInt<998244353>;

V<M> sum_inv(const V<M> &a, const V<M> &b, i32 m) {
    static constexpr FFTRoot<M::get_mod()> root{};
    assert(LEN(a) == LEN(b));
    const i32 old = LEN(a);
    const i32 lg = ceil_log2(LEN(a));
    const i32 n = 1 << lg;
    const i32 n2 = n * 2;
    V<M> c(n2), d(n2);
    REP(i, old) {
        c[2 * i] = c[2 * i + 1] = a[i];
        d[2 * i] = M(1) - b[i];
        d[2 * i + 1] = M(1) + b[i];
    }
    fill(begin(d) + 2 * old, end(d), M(1));
    REP(ph, lg) {
        const i32 w = 1 << (ph + 1), w2 = w * 2;
        M omega = root.root[ph + 2];
        for (i32 i = 0; i < n2; i += w2) {
            const i32 ti = i + w;
            REP(j, w) {
                c[ti + j] = c[i + j] = c[i + j] * d[ti + j] + c[ti + j] * d[i + j];
                d[ti + j] = d[i + j] *= d[ti + j];
            }
            ifft(c.data() + ti, w);
            ifft(d.data() + ti, w);
            d[ti] = M(2) - d[ti];
            M pw(1);
            REP(j, w) {
                c[ti + j] *= pw;
                d[ti + j] *= pw;
                pw *= omega;
            }
            fft(c.data() + ti, w);
            fft(d.data() + ti, w);
        }
    }
    ifft(c);
    ifft(d);
    c.resize(m);
    d = fps_inv(d, m);
    V<M> ans = convolve(c, d);
    ans.resize(m);
    return ans;
}

V<M> multieval(V<M> f, const V<M> &p) {
    static constexpr FFTRoot<M::get_mod()> root{};
    const i32 m = LEN(f);
    const i32 _n = LEN(p);
    const i32 lg = ceil_log2(_n);
    const i32 n = 1 << lg;
    const i32 n2 = n * 2;
    VV<M> tree(lg + 1, V<M>(n2));
    REP(i, _n) {
        tree[0][2 * i] = M(1) - p[i];
        tree[0][2 * i + 1] = M(1) + p[i];
    }
    fill(begin(tree[0]) + 2 * _n, end(tree[0]), M(1));
    REP(ph, lg) {
        const i32 w = 1 << (ph + 1), w2 = w * 2;
        M omega = root.root[ph + 2];
        V<M> &d = tree[ph + 1];
        d = tree[ph];
        for (i32 i = 0; i < n2; i += w2) {
            const i32 ti = i + w;
            REP(j, w) {
                d[ti + j] = d[i + j] *= d[ti + j];
            }
            ifft(d.data() + ti, w);
            d[ti] = M(2) - d[ti];
            M pw(1);
            REP(j, w) {
                d[ti + j] *= pw;
                pw *= omega;
            }
            fft(d.data() + ti, w);
        }
    }
    ifft(tree[lg]);
    tree[lg] = fps_inv(tree[lg], m);
    f.resize(2 * m - 1);
    V<M> c = middle_product(tree[lg], f);
    c.resize(n2);
    transposed_ifft(c);
    PER(ph, lg) {
        const i32 w = 1 << (ph + 1), w2 = w * 2;
        M omega = root.root[ph + 2];
        for (i32 i = 0; i < n2; i += w2) {
            const i32 ti = i + w;
            transposed_fft(c.data() + ti, w);
            M pw(1);
            REP(j, w) {
                c[ti + j] *= pw;
                pw *= omega;
            }
            transposed_ifft(c.data() + ti, w);
            REP(j, w) {
                M t = c[i + j] + c[ti + j];
                c[i + j] = t * tree[ph][ti + j];
                c[ti + j] = t * tree[ph][i + j];
            }
        }
    }
    V<M> ans(_n);
    REP(i, _n) {
        ans[i] = c[2 * i] + c[2 * i + 1];
    }
    return ans;
}

} // namespace Forested

vector<mint> multi(fps f, vector<mint> xs){
    int n = f.size(), m = xs.size();
    Forested::V<Forested::M> a(n), b(m); 
    rep(i,n){
        a[i] = f[i].val();
    }
    rep(j,m){
        b[j] = xs[j].val();
    }
    auto ans = Forested::multieval(a, b);
    vector<mint> ret(m);
    rep(j,m){
        ret[j] = ans[j].get_val();
    }
    return ret;
}

void solve(){
    // jikken1();
    // jikken2();
    int n; in(n);
    // assert(n <= 100000); // aaaaaaaaa
    fps f(n+1);
    rep(p,n+1){
        f[n-p] = mint(n-p).pow(n) * bnm.ifact(p) * bnm.ifact(n-p);
    }
    vector<mint> xs(n);
    rep(i,n){
        xs[i] = n * bnm.inv(i+1) - 1;
    }
    // auto ys = multipoint_evaluation(f, xs);
    auto ys = multi(f, xs);
    
    mint ans = 0;
    // i = 0
    rep(p,n+1){
        int i = 0;
        ans += mint(n-p).pow(n) * (i % 2 == 0 ? 1 : -1) * h2(p,i) * h2(n-p,n-i) * bnm(n+1,i+1);
    }
    // i = n
    // rep(p,n+1){
    //     int i = n;
    //     ans += mint(n-p).pow(n) * (i % 2 == 0 ? 1 : -1) * h2(p,i) * h2(n-p,n-i) * bnm(n+1,i+1);
    // }
    repp(i,1,n+1){
        ans += (i % 2 == 0 ? 1 : -1) * bnm(n+1,i+1) * mint(i).pow(n) * ys[i-1];
    }
    ans *= bnm.fact(n);
    ans -= mint(n).pow(n*2);
    out(ans);
}

int main(){
    int t = 1; //in(t);
    while (t--) { solve(); }
}