#line 2 "/Users/korogi/Desktop/cp-cpp/template.hpp"
#include <bits/stdc++.h>
using namespace std;

using i32 = int;
using i64 = long long;
using i128 = __int128;
using u32 = unsigned int;
using u64 = unsigned long long;
using u128 = unsigned __int128;
using f32 = double;
using f64 = long double;

#define DMP(x) cout << "[" << __LINE__ << "]" << " " << #x << ":" << " " << x << endl;

#define FOR1(n)          for(int _ =  0 , n_ = (n); _ < n_; _++)
#define FOR2(i, n)       for(int i =  0 , n_ = (n); i < n_; i++)
#define FOR3(i, s, t)    for(int i = (s), t_ = (t); i < t_; i++)
#define FOR4(i, s, t, d) for(int i = (s), t_ = (t), d_ = (d); i < t_; i += d_)
#define OVERLOAD4(a, b, c, d, e, ...) e
#define FOR(...) OVERLOAD4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)

#define REV1(n)          for(int _ = (n) - 1; _ >=  0 ; _--)
#define REV2(i, n)       for(int i = (n) - 1; i >=  0 ; i--)
#define REV3(i, s, t)    for(int i = (t) - 1, s_ = (s); i >= s_; i--)
#define REV4(i, s, t, d) for(int i = (t) - 1, s_ = (s), d_ = (d); i >= s_; i -= d_)
#define OVERLOAD3(a, b, c, d, ...) d
#define REV(...) OVERLOAD4(__VA_ARGS__, REV4, REV3, REV2, REV1)(__VA_ARGS__)

#define FOR_SUBSET(T, S) for(int S_ = (S), T = S_; T >= 0; T = (T == 0 ? -1 : (T - 1) & S_))

#define MULTI for(int testcase_ = in(), testcase = 0; testcase < testcase_; testcase++) [&]

template < class T > using heap_max = priority_queue< T, vector< T >, less< T > >;
template < class T > using heap_min = priority_queue< T, vector< T >, greater< T >>;

template < class T, class U > bool chmin(T& a, const U& b) { return a > b ? a = b, 1 : 0; }
template < class T, class U > bool chmax(T& a, const U& b) { return a < b ? a = b, 1 : 0; }

i64 floor_div(const i64 n, const i64 d) { assert(d != 0); return n / d - ((n ^ d) <  0 && n % d != 0); }
i64  ceil_div(const i64 n, const i64 d) { assert(d != 0); return n / d + ((n ^ d) >= 0 && n % d != 0); }

template < class T, class F > T bin_search(T ok, T ng, F check) { while(abs(ok - ng) > 1) { T mid = (ok + ng) / 2; (check(mid) ? ok : ng) = mid; } return ok; }
template < class T, class F > T bin_search_real(T ok, T ng, F check, int step = 100) { FOR(step) { T mid = (ok + ng) / 2; (check(mid) ? ok : ng) = mid; } return ok; }

template < class T, class U > T accum(const vector< U >& a) { return accumulate(a.begin(), a.end(), T(0)); }
template < class T > void sort(vector< T >& a) { sort(a.begin(), a.end()); }
template < class T > void rsort(vector< T >& a) { sort(a.rbegin(), a.rend()); }
template < class T > void reverse(vector< T >& a) { reverse(a.begin(), a.end()); }
void sort(string& s) { sort(s.begin(), s.end()); }
void rsort(string& s) { sort(s.rbegin(), s.rend()); }
void reverse(string& s) { reverse(s.begin(), s.end()); }
template < class T, class Cmp > void sort(vector< T >& a, Cmp cmp) { sort(a.begin(), a.end(), cmp); }
template < class T > int LB(const vector< T >& a, T x) { return distance(a.begin(), lower_bound(a.begin(), a.end(), x)); }
template < class T > int UB(const vector< T >& a, T x) { return distance(a.begin(), upper_bound(a.begin(), a.end(), x)); }
template < class T > void unique(vector< T >& a) { sort(a.begin(), a.end()); a.erase(unique(a.begin(), a.end()), a.end()); }
vector<int> iota(int n) { vector<int> a(n); iota(a.begin(), a.end(), 0); return a; }

istream& operator >> (istream& is, i128& x) {
    string s; is >> s;
    int m = (s[0] == '-');
    x = 0;
    FOR(i, m, ssize(s)) x = x * 10 + (s[i] - '0');
    if(m) x *= -1;
    return is;
}
ostream& operator << (ostream& os, const i128& x) {
    if(x == 0) return os << '0';
    i128 y = x; if(y < 0) { os << '-'; y *= -1; }
    vector<int> ny;
    while(y) ny.push_back(y % 10), y /= 10;
    REV(i, ssize(ny)) os << ny[i];
    return os;
}
namespace scan {
struct x0 { template < class T > operator T() { T x; cin >> x; return x; } };
struct x1 { int n; x1(int n) : n(n) {} template < class T > operator vector< T >() { vector< T > a(n); for(T& x : a) cin >> x; return a; } };
struct x2 { int h, w; x2(int h, int w) : h(h), w(w) {} template < class T > operator vector< vector< T > >() { vector m(h, vector< T >(w)); for(vector< T >& a : m) for(T& x : a) cin >> x; return m; } };
struct cppio { cppio() { cin.tie(0); ios::sync_with_stdio(0); } } cppio_instance;
}
scan::x0 in() { return scan::x0(); }
scan::x1 in(int n) { return scan::x1(n); }
scan::x2 in(int h, int w) { return scan::x2(h, w); }

template < class T > ostream& operator << (ostream& os, const vector< T >& a) {
    const int n = a.size();
    FOR(i, n) { os << a[i]; if(i + 1 != n) os << ' '; }
    return os;
}
template < class T > int print_n(const vector< T >& a) { for(const T& x : a) cout << x << '\n'; return 0; }
int print() { cout << '\n'; return 0; }
template < class Head, class... Tail > int print(Head&& h, Tail&&... t) { cout << h; if(sizeof...(Tail)) cout << ' '; return print(forward<Tail>(t)...); }
namespace printer {
    void prec(int n) { cout << fixed << setprecision(n); }
    void flush() { cout.flush(); }
}

vector<int>& operator ++ (vector<int>& a) { for(auto& e : a) e++; return a; }
vector<int>& operator -- (vector<int>& a) { for(auto& e : a) e--; return a; }
vector<int>  operator ++ (vector<int>& a, int) { vector<int> b = a; ++a; return b; }
vector<int>  operator -- (vector<int>& a, int) { vector<int> b = a; --a; return b; }

template < class T > vector<pair< T, int>> RLE(const vector< T >& a) { vector<pair< T, int>> v; for(const T& x : a) { if(not v.empty() and v.back().first == x) v.back().second++; else v.emplace_back(x, 1); } return v; }
vector<pair<char, int>> RLE(const string& s) { vector<pair<char, int>> v; for(const char& c : s) { if(not v.empty() and v.back().first == c) v.back().second++; else v.emplace_back(c, 1); } return v; }
template < class String, class Same > vector<String> RLE(const String& a, const Same same) { vector<String> v; for(const auto& x : a) { if(not v.empty() and same(v.back().back(), x)) v.back().push_back(x); else v.push_back({x}); } return v; }

int YESNO(bool yes) { return print(yes ? "YES" : "NO"); }
int YesNo(bool yes) { return print(yes ? "Yes" : "No"); }
int Yes() { return print("Yes"); }
int No() { return print("No"); }

constexpr i32 INF32 = 1e9;
constexpr i64 INF64 = 1e18;
template < class T > constexpr T infty = 0;
template <> constexpr int infty<int> = 1e9;
template <> constexpr int infty<u32> = 1e9;
template <> constexpr i64 infty<i64> = 1e18;
template <> constexpr u64 infty<u64> = 1e18;

namespace bit {
int pop(int x) { return popcount<u32>(x); }
int pop(u32 x) { return popcount<u32>(x); }
int pop(i64 x) { return popcount<u64>(x); }
int pop(u64 x) { return popcount<u64>(x); }
int parity(int x) { return __builtin_parity(x); }
int parity(u32 x) { return __builtin_parity(x); }
int parity(i64 x) { return __builtin_parityll(x); }
int parity(u64 x) { return __builtin_parityll(x); }
int sgn(int x) { return parity(x) ? -1 : +1; }
int sgn(u32 x) { return parity(x) ? -1 : +1; }
int sgn(i64 x) { return parity(x) ? -1 : +1; }
int sgn(u64 x) { return parity(x) ? -1 : +1; }
int top(int x) { return x == 0 ? -1 : 31 - __builtin_clz(x); }
int top(u32 x) { return x == 0 ? -1 : 31 - __builtin_clz(x); }
int top(i64 x) { return x == 0 ? -1 : 63 - __builtin_clzll(x); }
int top(u64 x) { return x == 0 ? -1 : 63 - __builtin_clzll(x); }
int low(int x) { return x == 0 ? -1 : __builtin_ctz(x); }
int low(u32 x) { return x == 0 ? -1 : __builtin_ctz(x); }
int low(i64 x) { return x == 0 ? -1 : __builtin_ctzll(x); }
int low(u64 x) { return x == 0 ? -1 : __builtin_ctzll(x); }
int ceil(int x) { return bit_ceil<u32>(x); }
}

// (-1)^n
int parity_sign(int n) { return n % 2 == 0 ? +1 : -1; }

// template < class T > pair< T, int > min(const vector< T >& a) { auto itr = min_element(a.begin(), a.end()); return {*itr, itr - a.begin()}; }
// template < class T > pair< T, int > max(const vector< T >& a) { auto itr = max_element(a.begin(), a.end()); return {*itr, itr - a.begin()}; }

template < class Key, class Value >
struct key_value {
    Key key;
    Value value;
};
template < class Value > key_value<int, Value> min(const vector<Value>& a) {
    assert(1 <= ssize(a));
    auto itr = min_element(a.begin(), a.end());
    return {itr - a.begin(), *itr};
}
template < class Value > key_value<int, Value> max(const vector<Value>& a) {
    assert(1 <= ssize(a));
    auto itr = max_element(a.begin(), a.end());
    return {itr - a.begin(), *itr};
}

struct grid {
    int H, W;
    grid(int H, int W) : H(H), W(W) {}
    static constexpr pair<int, int> dir4[] = {
                  {-1,  0}, 
        { 0, -1},           { 0, +1}, 
                  {+1,  0}
    };
    static constexpr pair<int, int> dir8[] = {
        {-1, -1}, {-1,  0}, {-1, +1},
        { 0, -1},           { 0, +1},
        {+1, -1}, {+1,  0}, {+1, +1}
    };
    bool contains(int i, int j) const {
        return 0 <= i and i < H and 0 <= j and j < W;
    }
    template < class F > 
    void for_each_dir4(int i, int j, const F& f) const {
        for(const auto [di, dj] : dir4) {
            const int ni = i + di, nj = j + dj;
            if(contains(ni, nj)) f(ni, nj);
        }
    }
    template < class F >
    void for_each_dir8(int i, int j, const F& f) const {
        for(const auto [di, dj] : dir8) {
            const int ni = i + di, nj = j + dj;
            if(contains(ni, nj)) f(ni, nj);
        }
    }
};

template < class Sum > struct psum1D {
    int n;
    vector<Sum> s;
    psum1D() : n(0), s(1, Sum()) {}
    template < class Value >
    psum1D(const vector<Value>& a) : n(ssize(a)), s(n + 1, Sum()) {
        FOR(i, n) s[i + 1] = s[i] + static_cast<Sum>(a[i]);
    }
    // [l, r)
    Sum v(int l, int r) const {
        assert(0 <= l and l <= r and r <= n);
        return s[r] - s[l];
    }
    void push_back(const Sum& x) {
        s.push_back(s.back() + x);
        n += 1;
    }
};

template < class Value > struct psum2D {
    int H, W;
    vector<vector<Value>> A;
    bool built;
    psum2D(int H, int W) : H(H), W(W), A(H + 1, vector(W + 1, Value(0))), built(false) {}
    // A[x][y] += v
    void add(int x, int y, Value v) {
        assert(not built);
        assert(0 <= x and x < H);
        assert(0 <= y and y < W);
        A[x + 1][y + 1] += v;
    }
    void build() {
        FOR(x, H) FOR(y, W + 1) A[x + 1][y] += A[x][y];
        FOR(x, H + 1) FOR(y, W) A[x][y + 1] += A[x][y];
        built = true;
    }
    // [xL, xR) * [yL, yR)
    Value sum(int xL, int xR, int yL, int yR) {
        assert(built);
        assert(0 <= xL and xL <= xR and xR <= H);
        assert(0 <= yL and yL <= yR and yR <= W);
        return A[xR][yR] - A[xR][yL] - A[xL][yR] + A[xL][yL];
    }
};

#line 3 "/Users/korogi/Desktop/cp-cpp/rnd.hpp"

namespace rnd {
    u32 seed; mt19937 mt;
    struct gen_seed { gen_seed() { seed = random_device()(); mt = mt19937(seed); } } gen_seed_instance;
    // [L, R)
    template < class Int > Int i(Int L, Int R) { assert(L < R); return uniform_int_distribution<Int>(L, R - 1)(mt); }
    template < class Real > Real r(Real L, Real R) { assert(L <= R); return uniform_real_distribution<Real>(L, R)(mt); }
}

template < int n, array<u32, n> mod > struct hash_vector {
    array<u32, n> a;
    using hvec = hash_vector;
    hvec& s(array<u32, n> a) { FOR(i, n) this->a[i] = a[i] < mod[i] ? a[i] : a[i] - mod[i]; return *this; }
    hash_vector(u32 v = 0) { FOR(i, n) a[i] = v % mod[i] + mod[i]; s(a); }
    hvec operator - () const { return hvec() - *this; }
    hvec& operator += (const hvec& r) { FOR(i, n) a[i] += r.a[i]; return s(a); }
    hvec& operator -= (const hvec& r) { FOR(i, n) a[i] += mod[i] - r.a[i]; return s(a); }
    hvec& operator *= (const hvec& r) { FOR(i, n) a[i] = u64(a[i]) * r.a[i] % mod[i]; return *this; }
    hvec& operator /= (const hvec& r) { return *this *= inv(r); }
    hvec operator + (const hvec& r) const { return hvec(*this) += r; }
    hvec operator - (const hvec& r) const { return hvec(*this) -= r; }
    hvec operator * (const hvec& r) const { return hvec(*this) *= r; }
    hvec operator / (const hvec& r) const { return hvec(*this) /= r; }
    bool operator == (const hvec& r) const { return a == r.a; }
    bool operator != (const hvec& r) const { return a != r.a; }
    bool operator < (const hvec& r) const { return a < r.a; }
};
template < int n, array<u32, n> mod > hash_vector<n, mod> pow(hash_vector<n, mod> x, u64 m) {
    hash_vector<n, mod> p(1);
    for(; m; m >>= 1) { if(m & 1) p *= x; x *= x; }
    return p;
}
template < int n, array<u32, n> mod > hash_vector<n, mod> inv(hash_vector<n, mod> x) {
    hash_vector<n, mod> res;
    FOR(i, n) {
        u32 a = x.a[i], b = mod[i], u = 1, v = 0;
        while(b) { u32 t = a / b; swap(a -= t * b, b); swap(u -= t * v, v); }
        res[i] = u;
    }
    return res;
}
template < int n, array<u32, n> mod > ostream& operator << (ostream& os, const hash_vector< n, mod >& x) { FOR(i, n) { if(i) os << ' '; os << x.a[i]; } return os; }
using hvec1 = hash_vector< 1, array<u32, 1>{999999937} >;
using hvec2 = hash_vector< 2, array<u32, 2>{999999937, 1000000007} >;
using hvec3 = hash_vector< 3, array<u32, 3>{999999937, 1000000007, 1000000009} >;
using hvec4 = hash_vector< 4, array<u32, 4>{999999937, 1000000007, 1000000009, 1000000021} >;
#line 3 "/Users/korogi/Desktop/cp-cpp/mod/modint.hpp"

template < u32 mod_, u32 prime_, u32 root_ > struct static_modint {
    static constexpr u32 const & mod = mod_;
    static constexpr u32 const & prime = prime_;
    static constexpr u32 const & root = root_;
    u32 v;
    using mint = static_modint;
    constexpr mint& s(u32 v) { this->v = v < mod ? v : v - mod; return *this; }
    constexpr static_modint(i64 v = 0) { s(v % mod + mod); }
    mint operator - () const { return mint() - *this; }
    mint operator + () const { return *this; }
    mint& operator += (const mint& r) { return s(v + r.v); }
    mint& operator -= (const mint& r) { return s(v + mod - r.v); }
    mint& operator *= (const mint& r) { v = u64(v) * r.v % mod; return *this; }
    mint& operator /= (const mint& r) { return *this *= inv(r); }
    mint operator + (const mint& r) const { return mint(*this) += r; }
    mint operator - (const mint& r) const { return mint(*this) -= r; }
    mint operator * (const mint& r) const { return mint(*this) *= r; }
    mint operator / (const mint& r) const { return mint(*this) /= r; }
    bool operator == (const mint& r) const { return v == r.v; }
    bool operator != (const mint& r) const { return v != r.v; }
};
// x^n
template < u32 mod, u32 prime, u32 root > static_modint<mod, prime, root> pow(static_modint<mod, prime, root> x, u64 n) {
    static_modint<mod, prime, root> p(1);
    for(; n; n >>= 1) { if(n & 1) p *= x; x *= x; }
    return p;
}
// x^{-1}
template < u32 mod, u32 prime, u32 root > static_modint<mod, prime, root> inv(static_modint<mod, prime, root> x) {
    int a = x.v, b = mod, u = 1, v = 0;
    while(b) { int t = a / b; swap(a -= t * b, b); swap(u -= t * v, v); }
    return static_modint<mod, prime, root>(u);
}
template < u32 mod, u32 prime, u32 root > istream& operator >> (istream& is, static_modint<mod, prime, root>& x) { i64 v; is >> v; x = static_modint<mod, prime, root>(v); return is; }
template < u32 mod, u32 prime, u32 root > ostream& operator << (ostream& os, const static_modint<mod, prime, root>& x) { return os << x.v; }

using modint998 = static_modint<  998'244'353, 1, 3>;
using modint107 = static_modint<1'000'000'007, 1, 5>;
#line 3 "a.cpp"
using mint = modint998;
#line 3 "/Users/korogi/Desktop/cp-cpp/mod/binom.hpp"

namespace comb {
template < class mint > mint fact(int n) {
    static const u32 mod = mint::mod;
    assert(0 <= n); assert(n < mod); assert(mint::prime);
    static vector<mint> data = {1, 1};
    while(ssize(data) <= n) { const int i = ssize(data); data.push_back(data.back() * i); }
    return data[n];
}
template < class mint > mint inv(int n) {
    static const u32 mod = mint::mod;
    assert(0 <= n); assert(n < mod); assert(mint::prime);
    static vector<mint> data = {1, 1};
    while(ssize(data) <= n) { const int i = ssize(data); data.push_back(-data[mod % i] * (mod / i)); }
    return data[n];
}
template < class mint > mint fact_inv(int n) {
    static const u32 mod = mint::mod;
    assert(0 <= n); assert(n < mod); assert(mint::prime);
    static vector<mint> data = {1, 1};
    while(ssize(data) <= n) { const int i = ssize(data); data.push_back(data.back() * inv<mint>(i)); }
    return data[n];
}
template < class mint > mint comb(int n, int k) {
    return 0 <= k and k <= n ? fact<mint>(n) * fact_inv<mint>(k) * fact_inv<mint>(n - k) : 0;
}
template < class mint > mint catalan(int n) {
    assert(0 <= n);
    return comb<mint>(n + n, n) * inv<mint>(n + 1);
}
}

template < class T > struct powers {
    T a; vector< T > data;
    powers(const T a) : a(a), data({1}) {}
    // a^n
    T get(int n) {
        assert(0 <= n);
        while(ssize(data) <= n) data.push_back(data.back() * a);
        return data[n];
    }
};
#line 4 "/Users/korogi/Desktop/cp-cpp/mod/ntt.hpp"

namespace ntt {

template < class mint > void ntt(vector<mint>& a, bool is_inv) {
    const int n = ssize(a);
    if(n == 0) return;
    static u32 mod = mint::mod, root = mint::root;
    static bool init = true;
    static mint bw[30], ibw[30];
    if(init) {
        init = false;
        FOR(k, 30) ibw[k] = inv(bw[k] = pow(mint(root), (mod - 1) >> (k + 1)));
    }

    for(int i = 0, j = 1; j + 1 < n; j++) {
        for(int k = n >> 1; k > (i ^= k); k >>= 1);
        if(i > j) swap(a[i], a[j]);
    }
    for(int k = 0, t = 2; t <= n; k++, t <<= 1) {
        mint b = not is_inv ? bw[k] : ibw[k];
        for(int i = 0; i < n; i += t) {
            mint w = 1;
            for(int j = 0; j < t / 2; j++) {
                int j1 = i + j, j2 = i + j + t / 2;
                mint c1 = a[j1], c2 = a[j2] * w;
                a[j1] = c1 + c2;
                a[j2] = c1 - c2;
                w *= b;
            }
        }
    }
    if(is_inv) {
        mint x = inv(mint(n));
        FOR(i, n) a[i] *= x;
    }
}

template < class mint > vector<mint> naive(const vector<mint>& a, const vector<mint>& b) {
    const int n = ssize(a), m = ssize(b);
    if(n == 0 or m == 0) return {};
    vector<mint> c(n + m - 1, 0);
    FOR(i, n) FOR(j, m) c[i + j] += a[i] * b[j];
    return c;
}

using mint0 = static_modint<754'974'721, 1, 11>;
using mint1 = static_modint<167'772'161, 1,  3>;
using mint2 = static_modint<469'762'049, 1,  3>;
const mint1 imod0 ( 95'869'806); // m0^-1 mod m1
const mint2 imod1 (104'391'568); // m1^-1 mod m2
const mint2 imod01(187'290'749); // imod1 / m0

template < class mint > vector<mint> conv(vector<mint> a, vector<mint> b) {
    const int n = ssize(a), m = ssize(b);
    if(min(n, m) < 30) return naive(a, b);
    const u32 mod = mint::mod;
    const int sz = [&] {
        int n2 = 1; while(n2 < n) n2 <<= 1;
        int m2 = 1; while(m2 < m) m2 <<= 1;
        return max(n2, m2) << 1;
    }();

    if(mod == 998'244'353) {
        a.resize(sz); ntt(a, false);
        b.resize(sz); ntt(b, false);
        vector<mint> c(sz);
        FOR(i, sz) c[i] = a[i] * b[i];
        ntt(c, true); c.resize(n + m - 1);
        return c;
    }

    vector<mint0> a0(sz), b0(sz), c0(sz);
    vector<mint1> a1(sz), b1(sz), c1(sz);
    vector<mint2> a2(sz), b2(sz), c2(sz);
    FOR(i, n) a0[i].v = a1[i].v = a2[i].v = a[i].v;
    FOR(i, m) b0[i].v = b1[i].v = b2[i].v = b[i].v;
    ntt(a0, false); ntt(a1, false); ntt(a2, false);
    ntt(b0, false); ntt(b1, false); ntt(b2, false);
    FOR(i, sz) c0[i] = a0[i] * b0[i];
    FOR(i, sz) c1[i] = a1[i] * b1[i];
    FOR(i, sz) c2[i] = a2[i] * b2[i];
    ntt(c0, true); ntt(c1, true); ntt(c2, true);
    vector<mint> c(n + m - 1);
    const mint mod0 = mint0::mod;
    const mint mod01 = mod0 * mint1::mod;
    FOR(i, n + m - 1) {
        i64 y0 = c0[i].v;
        i64 y1 = (imod0 * (c1[i] - y0)).v;
        i64 y2 = (imod01 * (c2[i] - y0) - imod1 * y1).v;
        c[i] = mod01 * y2 + mod0 * y1 + y0;
    }
    return c;
}

// a^2
template < class mint > vector<mint> square(vector<mint> a) {
    const int n = ssize(a);
    if(n < 30) return naive(a, a);
    const u32 mod = mint::mod;
    const int sz = [&] {
        int n2 = 1; while(n2 < n) n2 <<= 1;
        return n2 << 1;
    }();

    if(mod == 998'244'353) {
        a.resize(sz); ntt(a, false);
        vector<mint> c(sz);
        FOR(i, sz) c[i] = a[i] * a[i];
        ntt(c, true); c.resize(n + n - 1);
        return c;
    }

    vector<mint0> a0(sz), c0(sz);
    vector<mint1> a1(sz), c1(sz);
    vector<mint2> a2(sz), c2(sz);
    FOR(i, n) a0[i].v = a1[i].v = a2[i].v = a[i].v;
    ntt(a0, false); ntt(a1, false); ntt(a2, false);
    FOR(i, sz) c0[i] = a0[i] * a0[i];
    FOR(i, sz) c1[i] = a1[i] * a1[i];
    FOR(i, sz) c2[i] = a2[i] * a2[i];
    ntt(c0, true); ntt(c1, true); ntt(c2, true);
    vector<mint> c(n + n - 1);
    const mint mod0 = mint0::mod;
    const mint mod01 = mod0 * mint1::mod;
    FOR(i, n + n - 1) {
        i64 y0 = c0[i].v;
        i64 y1 = (imod0 * (c1[i] - y0)).v;
        i64 y2 = (imod01 * (c2[i] - y0) - imod1 * y1).v;
        c[i] = mod01 * y2 + mod0 * y1 + y0;
    }
    return c;
}

}

template < class mint >
vector<mint> prod_all(const vector<vector<mint>>& fs) {
    if(ssize(fs) == 0) return {mint(1)};
    auto rec = [&](auto&& rec, int l, int r) -> vector<mint> {
        if(l + 1 == r) return fs[l];
        const int m = (l + r) / 2;
        return move(ntt::conv(move(rec(rec, l, m)), move(rec(rec, m, r))));
    };
    return rec(rec, 0, ssize(fs));
}
#line 4 "/Users/korogi/Desktop/cp-cpp/mod/fps.hpp"

template < class mint >
void fmt(const int n, mint* const f, bool is_inv) {
    static constexpr u32 mod = mint::mod;
    static constexpr u32 mod2 = mod * 2;
    static const int L = 30;
    static mint g[L], ig[L], p2[L];
    if(g[0].v == 0) {
        FOR(i, L) {
            mint w = -pow(mint(mint::root), ((mod - 1) >> (i + 2)) * 3);
            g[i] = w;
            ig[i] = inv(w);
            p2[i] = inv(mint(1 << i));
        }
    }

    if(not is_inv) {
        int b = n;
        if(b >>= 1) {
            FOR(i, b) {
                u32 x = f[i + b].v;
                f[i + b].v = f[i].v + mod - x;
                f[i].v += x;
            }
        }
        if(b >>= 1) {
            mint p = 1;
            int k = 0;
            FOR(i, 0, n, b * 2) {
                FOR(j, i, i + b) {
                    u32 x = (f[j + b] * p).v;
                    f[j + b].v = f[j].v + mod - x;
                    f[j].v += x;
                }
                p *= g[bit::low(++k)];
            }
        }
        while(b) {
            if(b >>= 1) {
                mint p = 1;
                int k = 0;
                FOR(i, 0, n, b * 2) {
                    FOR(j, i, i + b) {
                        u32 x = (f[j + b] * p).v;
                        f[j + b].v = f[j].v + mod - x;
                        f[j].v += x;
                    }
                    p *= g[bit::low(++k)];
                }
            }
            if(b >>= 1) {
                mint p = 1;
                int k = 0;
                FOR(i, 0, n, b * 2) {
                    FOR(j, i, i + b) {
                        u32 x = (f[j + b] * p).v;
                        f[j].v = (f[j].v < mod2 ? f[j].v : f[j].v - mod2);
                        f[j + b].v = f[j].v + mod - x;
                        f[j].v += x;
                    }
                    p *= g[bit::low(++k)];
                }
            }
        }
    } else {
        int b = 1;
        if(b < n / 2) {
            mint p = 1;
            int k = 0;
            FOR(i, 0, n, b * 2) {
                FOR(j, i, i + b) {
                    u64 x = f[j].v + mod - f[j + b].v;
                    f[j].v += f[j + b].v;
                    f[j + b].v = x * p.v % mod;
                }
                p *= ig[bit::low(++k)];
            }
            b <<= 1;
        }
        for(; b < n / 2; b <<= 1) {
            mint p = 1;
            int k = 0;
            FOR(i, 0, n, b * 2) {
                for(int j = i; j < i + b / 2; j++) {
                    u64 x = f[j].v + mod2 - f[j + b].v;
                    f[j].v += f[j + b].v;
                    f[j].v = (f[j].v) < mod2 ? f[j].v : f[j].v - mod2;
                    f[j + b].v = x * p.v % mod;
                }
                for(int j = i + b / 2; j < i + b; j++) {
                    u64 x = f[j].v + mod - f[j + b].v;
                    f[j].v += f[j + b].v;
                    f[j + b].v = x * p.v % mod;
                }
                p *= ig[bit::low(++k)];
            }
        }
        if(b < n) {
            FOR(i, b) {
                u32 x = f[i + b].v;
                f[i + b].v = f[i].v + mod2 - x;
                f[i].v += x;
            }
        }
        const mint z = p2[__lg(n)];
        FOR(i, n) f[i] *= z;
    }
}

template < class mint > void fmt(vector<mint>& f) { fmt(ssize(f), f.data(), false); }
template < class mint > void fmt_inv(vector<mint>& f) { fmt(ssize(f), f.data(), true); }

template < class mint >
vector<mint> convolution(vector<mint> a, vector<mint> b) {
    const int n = ssize(a);
    const int m = ssize(b);
    const int k = n + m - 1;
    if(min(n, m) < 30) {
        vector<mint> c(k);
        FOR(i, n) FOR(j, m) c[i + j] += a[i] * b[j];
        return c;
    }

    const int k2 = bit::ceil(k);
    a.resize(k2); fmt(a);
    b.resize(k2); fmt(b);
    FOR(i, k2) a[i] *= b[i];
    fmt_inv(a); a.resize(k);
    return a;
}

namespace fps {
template < class mint >
vector<mint> prod(const vector<mint>& f, const vector<mint>& g) {
    return ntt::conv(f, g);
}
template < class mint >
vector<mint> prefix(const vector<mint>& f, int n) {
    vector<mint> g(n);
    FOR(i, min(n, (int)ssize(f))) g[i] = f[i]; 
    return g;
}
template < class mint >
vector<mint> inv(const vector<mint>& f, int n) {
    assert(1 <= ssize(f) and f[0] != 0);
    vector<mint> g(n);
    g[0] = mint(1) / f[0];
    for(int m = 1; m < n; m *= 2) {
        vector<mint> fm = prefix(f, 2 * m);
        fmt(fm);
        vector<mint> gm = prefix(g, 2 * m);
        fmt(gm);
        FOR(i, 2 * m) fm[i] *= gm[i];
        fmt_inv(fm);
        FOR(i, m) fm[i] = 0;
        fmt(fm);
        FOR(i, 2 * m) fm[i] *= gm[i];
        fmt_inv(fm);
        FOR(i, m, min(2 * m, n)) g[i] -= fm[i];
    }
    return g;
}
template < class mint >
vector<mint> derivative(const vector<mint>& f) {
    const int n = ssize(f);
    vector<mint> g(max(0, n - 1));
    FOR(i, 1, n) g[i - 1] = f[i] * i;
    return g;
}
template < class mint >
vector<mint> integral(const vector<mint>& f) {
    const int n = ssize(f);
    vector<mint> g(n + 1);
    FOR(i, n) g[i + 1] = f[i] * comb::inv<mint>(i + 1);
    return g;
}
template < class mint >
vector<mint> log(const vector<mint>& f, int n) {
    assert(1 <= ssize(f) and f[0] == 1);
    if(n == 1) return {0};
    return integral(prefix(prod(derivative(prefix(f, n)), inv(f, n - 1)), n - 1));
}
template < class mint >
vector<mint> exp(vector<mint> f, int n) {
    if(ssize(f) == 0) { vector<mint> e(n); e[0] = 1; return e; }
    assert(1 <= ssize(f) and f[0] == 0);

    vector<mint> g{1}, gg;
    f.resize(n);
    f[0] = 1;
    vector<mint> h = derivative(f);
    for(int m = 1; m < n; m *= 2) {
        vector<mint> ff = prefix(f, m);
        ff.resize(2 * m);
        fmt(ff);

        if(m != 1) {
            vector<mint> f2(m);
            FOR(i, m) f2[i] = ff[i] * gg[i];
            fmt_inv(f2);
            f2.erase(f2.begin(), f2.begin() + m / 2);
            f2.resize(m);
            fmt(f2);
            FOR(i, m) f2[i] *= gg[i];
            fmt_inv(f2);
            FOR(i, m / 2) f2[i] = -f2[i];
            g.insert(g.end(), f2.begin(), f2.begin() + m / 2);
        }

        vector<mint> t = derivative(prefix(f, m));
        t.resize(m);
        {
            vector<mint> r(h.begin(), h.begin() + (m - 1));
            r.resize(m);
            fmt(r);
            FOR(i, m) r[i] *= ff[i];
            fmt_inv(r);
            FOR(i, m) t[i] -= r[i];
            t.insert(t.begin(), t.back());
            t.pop_back();
        }

        t.resize(2 * m);
        fmt(t);
        gg = g;
        gg.resize(2 * m);
        fmt(gg);
        FOR(i, 2 * m) t[i] *= gg[i];
        fmt_inv(t);
        t.resize(m);

        vector<mint> v(f.begin() + m, f.begin() + min(n, 2 * m));
        v.resize(m);
        t.insert(t.begin(), m - 1, 0);
        t.push_back(0);
        t = integral(move(t));
        FOR(i, m) v[i] -= t[m + i];

        v.resize(2 * m);
        fmt(v);
        FOR(i, 2 * m) v[i] *= ff[i];
        fmt_inv(v);
        v.resize(m);
        FOR(i, min(n - m, m)) f[m + i] = v[i];
    }
    return f;
}
template < class mint >
vector<mint> pow(vector<mint> f, i64 e, int n) {
    if(e == 0) { vector<mint> g(n, 0); g[0] = 1; return g; }
    int i = 0;
    while(i < ssize(f) and f[i] == 0) i += 1;
    if(i == ssize(f) or n <= i128(e) * i) return vector<mint>(n, 0);
    const mint c = f[i];
    const mint ic = inv(c);
    const int o = e * i;
    vector<mint> g(f.begin() + i, f.end());
    FOR(i, ssize(g)) g[i] *= ic;
    g = log(move(g), n - o);
    const mint me = mint(e);
    FOR(i, ssize(g)) g[i] *= me;
    g = exp(move(g), n - o);
    const mint ce = pow(c, e);
    FOR(i, ssize(g)) g[i] *= ce;
    g.insert(g.begin(), o, 0);
    return g;
}
template < class mint > 
vector<mint> inv_sparse(const vector<pair<int, mint>>& f, int n) {
    assert(1 <= ssize(f) and f[0].first == 0 and f[0].second != 0);
    vector<mint> g(n);
    g[0] = inv(f[0].second);
    FOR(i, 1, n) {
        mint& x = g[i];
        for(auto [k, fk] : f) {
            if(i < k) break;
            x += fk * g[i - k];
        }
        g[i] *= -g[0];
    }
    return g;
}
template < class mint >
vector<mint> pow_sparse(vector<pair<int, mint>> f, i64 e, int n) {
    if(e == 0) { vector<mint> g(n, 0); g[0] = 1; return g; }
    if(ssize(f) == 0 or n <= i128(e) * f[0].first) return vector<mint>(n, 0);
    const mint c = f[0].second;
    const mint ic = inv(c);
    const mint me = mint(e);
    const int d = f[0].first, o = e * d, m = n - o;
    for(auto &[i, fi] : f) i -= d, fi *= ic;
    vector<mint> g(m);
    g[0] = 1;
    FOR(i, 1, m) {
        mint& x = g[i];
        for(auto [k, fk] : f) {
            if(i < k) break;
            x += fk * g[i - k] * (me * k - (i - k));
        }
        x *= comb::inv<mint>(i);
    }
    const mint ce = pow(c, e);
    FOR(i, m) g[i] *= ce;
    g.insert(g.begin(), o, 0);
    return g;
}
} // namespace fps
#line 6 "a.cpp"

int main() {
    int N = in();
    vector<mint> F(N, 0);
    FOR(d, 1, N) F[d] = comb::fact_inv<mint>(d - 1) * d;
    F = fps::pow(F, N, 2 * (N - 1) + 1);
    mint ans = F[2 * (N - 1)];
    ans *= comb::fact<mint>(N - 2);
    ans /= pow(mint(N), N - 2);
    print(ans);
}