#line 1 "src\\test_cpverifier\\yukicoder\\0963.0.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/963"

#line 1 "src\\code\\math\\mint_s30.hpp"



#line 1 "src\\code\\util\\util.hpp"



#include <bits/stdc++.h>

namespace tifa_libs {

using i8 = int8_t;
using u8 = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;

template <class T>
using vec = std::vector<T>;
template <class T>
using vvec = vec<vec<T>>;
template <class T>
using vvvec = vec<vvec<T>>;
template <class T>
using pq = std::priority_queue<T>;
template <class T>
using pqg = std::priority_queue<T, vec<T>, std::greater<T>>;

template <class U, class T>
using vvp = vvec<std::pair<U, T>>;

template <class T>
using ptt = std::pair<T, T>;
template <class T>
using pt3 = std::tuple<T, T, T>;
template <class T>
using pt4 = std::tuple<T, T, T, T>;

#ifdef ONLINE_JUDGE
#undef assert
#define assert(x) 42
#endif

}  // namespace tifa_libs


#line 5 "src\\code\\math\\mint_s30.hpp"

namespace tifa_libs::math {

template <u32 MOD>
class mint_s30 {
  u32 v_{};

  static constexpr u32 get_r() {
    u32 t = 2, iv = MOD * (t - MOD * MOD);
    iv *= t - MOD * iv, iv *= t - MOD * iv;
    return iv * (MOD * iv - t);
  }
  static constexpr u32 redc(u64 x) { return (u32)((x + (u64)((u32)(x)*R) * MOD) >> 32); }
  static constexpr u32 norm(u32 x) { return x - (MOD & -((MOD - 1 - x) >> 31)); }

  static constexpr u32 MOD2 = MOD << 1;
  static constexpr u32 R = get_r();
  static constexpr u32 R2 = -(u64)(MOD) % MOD;
  static constexpr i32 SMOD = (i32)(MOD);

  static_assert(MOD & 1);
  static_assert(-R * MOD == 1);
  static_assert((MOD >> 30) == 0);
  static_assert(MOD != 1);

 public:
  static constexpr u32 mod() { return MOD; }
  static constexpr i32 smod() { return SMOD; }
  constexpr mint_s30() {}
  template <typename T, std::enable_if_t<std::is_integral_v<T>, int> = 0>
  constexpr mint_s30(T v) : v_(redc((u64)(v % SMOD + SMOD) * R2)) {}
  constexpr u32 val() const { return norm(redc(v_)); }
  constexpr i32 sval() const { return (i32)norm(redc(v_)); }
  constexpr bool is_zero() const { return v_ == 0 || v_ == MOD; }
  template <typename T, std::enable_if_t<std::is_integral_v<T>, int> = 0>
  explicit constexpr operator T() const { return (T)(val()); }
  constexpr mint_s30 operator-() const {
    mint_s30 res;
    res.v_ = (MOD2 & -(v_ != 0)) - v_;
    return res;
  }
  constexpr mint_s30 inv() const {
    i32 x1 = 1, x3 = 0, a = sval(), b = SMOD;
    while (b != 0) {
      i32 q = a / b, x1_old = x1, a_old = a;
      x1 = x3, x3 = x1_old - x3 * q, a = b, b = a_old - b * q;
    }
    return mint_s30(x1);
  }
  constexpr mint_s30 &operator+=(const mint_s30 &rhs) {
    v_ += rhs.v_ - MOD2, v_ += MOD2 & -(v_ >> 31);
    return *this;
  }
  constexpr mint_s30 &operator-=(const mint_s30 &rhs) {
    v_ -= rhs.v_, v_ += MOD2 & -(v_ >> 31);
    return *this;
  }
  constexpr mint_s30 &operator*=(const mint_s30 &rhs) {
    v_ = redc((u64)(v_)*rhs.v_);
    return *this;
  }
  constexpr mint_s30 &operator/=(const mint_s30 &rhs) { return operator*=(rhs.inv()); }
  constexpr mint_s30 pow(u64 e) const {
    for (mint_s30 res(1), x(*this);; x *= x) {
      if (e & 1) res *= x;
      if ((e >>= 1) == 0) return res;
    }
  }
  constexpr void swap(mint_s30 &rhs) {
    auto v = v_;
    v_ = rhs.v_, rhs.v_ = v;
  }
  friend constexpr mint_s30 operator+(const mint_s30 &lhs, const mint_s30 &rhs) { return mint_s30(lhs) += rhs; }
  friend constexpr mint_s30 operator-(const mint_s30 &lhs, const mint_s30 &rhs) { return mint_s30(lhs) -= rhs; }
  friend constexpr mint_s30 operator*(const mint_s30 &lhs, const mint_s30 &rhs) { return mint_s30(lhs) *= rhs; }
  friend constexpr mint_s30 operator/(const mint_s30 &lhs, const mint_s30 &rhs) { return mint_s30(lhs) /= rhs; }
  friend constexpr bool operator==(const mint_s30 &lhs, const mint_s30 &rhs) { return norm(lhs.v_) == norm(rhs.v_); }
  friend constexpr bool operator!=(const mint_s30 &lhs, const mint_s30 &rhs) { return norm(lhs.v_) != norm(rhs.v_); }
  friend constexpr bool operator<(const mint_s30 &lhs, const mint_s30 &rhs) { return lhs.val() < rhs.val(); }
  friend std::istream &operator>>(std::istream &is, mint_s30 &rhs) {
    i32 x;
    is >> x;
    rhs = mint_s30(x);
    return is;
  }
  friend std::ostream &operator<<(std::ostream &os, const mint_s30 &rhs) { return os << rhs.val(); }
  friend constexpr u32 abs(mint_s30 const &x) { return x.val(); }
};

}  // namespace tifa_libs::math


#line 1 "src\\code\\poly\\poly_ode.hpp"



#line 1 "src\\code\\poly\\poly_exp.hpp"



#line 1 "src\\code\\poly\\poly_ln.hpp"



#line 1 "src\\code\\poly\\poly_deriv.hpp"



#line 1 "src\\code\\poly\\poly.hpp"



#line 5 "src\\code\\poly\\poly.hpp"

namespace tifa_libs::math {

template <class Pldt>
class poly {
  Pldt p;

 public:
  using value_type = typename Pldt::value_type;
  using data_type = vec<value_type>;

  explicit constexpr poly(size_t sz = 1) : p(sz) {}
  explicit constexpr poly(std::initializer_list<value_type> v) : p(v) {}
  template <class T>
  explicit constexpr poly(vec<T> const &v) : p(v) {}

  constexpr friend std::istream &operator>>(std::istream &is, poly &poly) {
    for (auto &val : poly.p.d) is >> val;
    return is;
  }
  constexpr friend std::ostream &operator<<(std::ostream &os, const poly &poly) {
    if (!poly.size()) return os;
    for (size_t i = 1; i < poly.size(); ++i) os << poly[i - 1] << ' ';
    return os << poly.p.d.back();
  }

  constexpr size_t size() const { return p.d.size(); }
  constexpr data_type &data() { return p.d; }
  constexpr data_type const &data() const { return p.d; }

  constexpr value_type &operator[](size_t x) { return p.d[x]; }
  constexpr value_type operator[](size_t x) const { return p.d[x]; }
  constexpr value_type operator()(value_type x) const {
    value_type ans = 0;
    for (size_t i = size() - 1; ~i; --i) ans = ans * x + p.d[i];
    return ans;
  }

  template <class F>
  void apply_range(size_t l, size_t r, F f) {
    assert(l < r && r <= size());
    for (size_t i = l; i < r; ++i) f(i, p.d[i]);
  }
  template <class F>
  void apply(F f) { apply_range(0, size(), f); }
  constexpr void resize(size_t size) { p.d.resize(size); }
  constexpr poly pre(size_t size) const {
    poly _ = *this;
    _.resize(size);
    return _;
  }
  constexpr void strip() {
    auto it = std::find_if(p.d.rbegin(), p.d.rend(), [](auto const &x) { return x != 0; });
    p.d.resize(p.d.rend() - it);
    if (p.d.empty()) p.d.push_back(value_type(0));
  }
  constexpr void reverse() { std::reverse(p.d.begin(), p.d.end()); }

  void conv(poly const &r, size_t ans_size) { p.conv(r.p, ans_size); }
  void conv(poly const &r) { p.conv(r.p); }

  constexpr poly operator-() const {
    poly ret = *this;
    ret.apply([]([[maybe_unused]] size_t i, auto &v) { v = -v; });
    return ret;
  }

  friend poly operator+(poly p, value_type c) {
    p[0] += c;
    return p;
  }
  friend poly operator+(value_type c, poly const &p) { return p + c; }
  friend poly operator-(poly p, value_type c) {
    p[0] -= c;
    return p;
  }
  friend poly operator-(value_type c, poly const &p) { return p - c; }

  constexpr poly &operator*=(value_type c) {
    apply([&c]([[maybe_unused]] size_t i, auto &v) { v *= c; });
    return *this;
  }
  constexpr friend poly operator*(poly p, value_type c) { return p *= c; }
  constexpr friend poly operator*(value_type c, poly p) { return p *= c; }

  constexpr poly &operator+=(poly const &r) {
    if (!r.size()) return *this;
    resize(std::max(size(), r.size()));
    apply_range(0, r.size(), [&r](size_t i, auto &v) { v += r[i]; });
    return *this;
  }
  friend poly operator+(poly l, poly const &r) { return l += r; }

  constexpr poly &operator-=(poly const &r) {
    if (!r.size()) return *this;
    resize(std::max(size(), r.size()));
    apply_range(0, r.size(), [&r](size_t i, auto &v) { v -= r[i]; });
    return *this;
  }
  friend poly operator-(poly l, poly const &r) { return l -= r; }

  poly &operator*=(poly const &r) {
    if (!r.size()) {
      resize(1);
      p.d[0] = 0;
      return *this;
    }
    conv(r);
    return *this;
  }
  friend poly operator*(poly l, poly const &r) { return l *= r; }
};

}  // namespace tifa_libs::math


#line 5 "src\\code\\poly\\poly_deriv.hpp"

namespace tifa_libs::math {

template <class T>
inline poly<T> poly_deriv(poly<T> const &p) {
  auto _ = p;
  for (size_t i = 1; i < _.size(); ++i) _[i - 1] = _[i] * i;
  _.data().back() = 0;
  return _;
}

}  // namespace tifa_libs::math


#line 1 "src\\code\\poly\\poly_int.hpp"



#line 5 "src\\code\\poly\\poly_int.hpp"

namespace tifa_libs::math {

template <class T>
inline poly<T> poly_int(poly<T> const &p) {
  using mint = typename T::value_type;
  auto _ = p;
  for (size_t i = _.size() - 1; i; --i) _[i] = _[i - 1] * mint(i).inv();
  _[0] = 0;
  return _;
}

}  // namespace tifa_libs::math


#line 1 "src\\code\\poly\\poly_inv.hpp"



#line 5 "src\\code\\poly\\poly_inv.hpp"

namespace tifa_libs::math {

template <class T>
inline poly<T> poly_inv(poly<T> const &p, size_t n = 0) {
  assert(p[0] != 0);
  if (!n) n = p.size();
  poly<T> a{p[0].inv()};
  for (size_t i = 1; i < n; i *= 2) a = (a * 2 - (a * a * p).pre(i * 2)).pre(i * 2);
  return a.pre(n);
}

}  // namespace tifa_libs::math


#line 7 "src\\code\\poly\\poly_ln.hpp"

namespace tifa_libs::math {

template <class T>
inline poly<T> poly_ln(poly<T> const &p, size_t n = 0) {
  assert(p[0] == 1);
  if (!n) n = p.size();
  auto _ = poly_deriv(p).pre(n);
  _.conv(poly_inv(p, n));
  return poly_int(_).pre(n);
}

}  // namespace tifa_libs::math


#line 5 "src\\code\\poly\\poly_exp.hpp"

namespace tifa_libs::math {

template <class T>
inline poly<T> poly_exp(poly<T> const &p, size_t n = 0) {
  assert(p[0] == 0);
  if (!n) n = p.size();
  poly<T> _ = p + 1, a{1};
  for (size_t i = 1; i < n; i *= 2) a = (a * (_.pre(i * 2) - poly_ln(a, i * 2))).pre(i * 2);
  return a.pre(n);
}

}  // namespace tifa_libs::math


#line 7 "src\\code\\poly\\poly_ode.hpp"

namespace tifa_libs::math {

template <class T, class G, class DG>
inline poly<T> poly_ode(G g, DG dg, typename T::value_type a, size_t n) {
  poly<T> f{a};
  for (size_t i = 1; i < n; i *= 2) {
    poly<T> r = poly_exp(poly_int(-dg(f, i * 2))), h = poly_int(((g(f, i * 2) - dg(f, i * 2) * f) * r).pre(i * 2));
    f = ((h + a) * poly_inv(r, i * 2)).pre(i * 2);
  }
  return f.pre(n);
}

}  // namespace tifa_libs::math


#line 1 "src\\code\\poly\\polydata_s.hpp"



#line 1 "src\\code\\poly\\conv_naive.hpp"



#line 5 "src\\code\\poly\\conv_naive.hpp"

namespace tifa_libs::math {

template <class T>
inline vec<T> conv_naive(vec<T> const &l, vec<T> const &r, size_t ans_size) {
  size_t n = l.size(), m = r.size();
  vec<T> ans(ans_size);
  if (n < m)
    for (size_t j = 0; j < m; ++j)
      for (size_t i = 0; i < n; ++i) {
        if (i + j >= ans_size) break;
        ans[i + j] += l[i] * r[j];
      }
  else
    for (size_t i = 0; i < n; ++i)
      for (size_t j = 0; j < m; ++j) {
        if (i + j >= ans_size) break;
        ans[i + j] += l[i] * r[j];
      }
  return ans;
}
template <class T>
inline vec<T> conv_naive(vec<T> const &l, vec<T> const &r) { return conv_naive(l, r, l.size() + r.size() - 1); }

}  // namespace tifa_libs::math


#line 1 "src\\code\\poly\\conv_ntt.hpp"



#line 1 "src\\code\\poly\\ntt.hpp"



#line 1 "src\\code\\bit\\bceil.hpp"



#line 1 "src\\code\\bit\\cntl0.hpp"



namespace tifa_libs::bit {

// From GCC lib
template <typename T>
constexpr int cntl0(T x) {
  constexpr int nd = sizeof(T) * 8;
  if (x == 0) return nd;
  static_assert(nd <= 128);
  constexpr int nd_ull = sizeof(unsigned long long) * 8;
  constexpr int nd_ul = sizeof(unsigned long) * 8;
  constexpr int nd_u = sizeof(unsigned) * 8;
  if constexpr (nd <= nd_u) return __builtin_clz(x) - (nd_u - nd);
  else if constexpr (nd <= nd_ul) return __builtin_clzl(x) - (nd_ul - nd);
  else if constexpr (nd <= nd_ull) return __builtin_clzll(x) - (nd_ull - nd);
  else {
    unsigned long long hi = x >> nd_ull;
    if (hi != 0) return __builtin_clzll(hi) - ((2 * nd_ull) - nd);
    unsigned long long lo = x & (unsigned long long)(-1);
    return (nd - nd_ull) + __builtin_clzll(lo);
  }
}

}  // namespace tifa_libs::bit


#line 6 "src\\code\\bit\\bceil.hpp"

namespace tifa_libs::bit {

// From GCC lib
template <typename T>
constexpr T bceil(T x) {
  if (x == 0 || x == 1) return 1;
  constexpr int nd = sizeof(T) * 8;
  int sh = nd - cntl0((T)(x - 1u));
  using U = decltype(x << 1);
  if constexpr (!std::is_same_v<U, T>) sh |= (sh & nd) << (sizeof(U) / sizeof(T) / 2);
  return (T)1u << sh;
}

}  // namespace tifa_libs::bit


#line 1 "src\\code\\math\\proot_u64.hpp"



#line 1 "src\\code\\math\\pfactors.hpp"



#line 1 "src\\code\\bit\\cntr0.hpp"



namespace tifa_libs::bit {

// From GCC lib
template <typename T>
constexpr int cntr0(T x) {
  constexpr int nd = sizeof(T) * 8;
  static_assert(nd <= 128);
  if (x == 0) return nd;
  constexpr int nd_ull = sizeof(unsigned long long) * 8;
  constexpr int nd_ul = sizeof(unsigned long) * 8;
  constexpr int nd_u = sizeof(unsigned) * 8;
  if constexpr (nd <= nd_u) return __builtin_ctz(x);
  else if constexpr (nd <= nd_ul) return __builtin_ctzl(x);
  else if constexpr (nd <= nd_ull) return __builtin_ctzll(x);
  else {
    unsigned long long lo = x & (unsigned long long)(-1);
    if (lo != 0) return __builtin_ctzll(lo);
    unsigned long long hi = x >> nd_ull;
    return __builtin_ctzll(hi) + nd_ull;
  }
}

}  // namespace tifa_libs::bit


#line 1 "src\\code\\rand\\gen.hpp"



#line 5 "src\\code\\rand\\gen.hpp"

namespace tifa_libs::rand {

template <class Distri>
class Gen {
  std::conditional_t<sizeof(typename Distri::result_type) <= 4, std::mt19937, std::mt19937_64> re;
  Distri dist;

 public:
  using random_engine = decltype(re);
  using distribution = Distri;
  using result_type = typename Distri::result_type;

  Gen() : re(std::random_device{}()), dist() {}
  Gen(result_type a, result_type b) : re(std::random_device{}()), dist(a, b) {}

  void set_range(result_type a, result_type b) { dist = Distri(a, b); }
  random_engine& rand_eng() { return re; }
  Distri& distrib() { return dist; }

  result_type operator()() { return dist(re); }
};

}  // namespace tifa_libs::rand


#line 1 "src\\code\\math\\is_prime.hpp"



#line 1 "src\\code\\math\\mul_mod_u.hpp"



#line 1 "src\\code\\bit\\bwidth.hpp"



#line 5 "src\\code\\bit\\bwidth.hpp"

namespace tifa_libs::bit {

// From GCC lib
template <typename T>
constexpr int bwidth(T x) { return (int)sizeof(T) * 8 - cntl0(x); }

}  // namespace tifa_libs::bit


#line 6 "src\\code\\math\\mul_mod_u.hpp"

namespace tifa_libs::math {

constexpr u64 mul_mod_u(u64 a, u64 b, u64 mod) {
  if (bit::bwidth(a) + bit::bwidth(b) <= 64) return a * b % mod;
  else return (u64)((u128)a * b % mod);
}

}  // namespace tifa_libs::math


#line 1 "src\\code\\math\\qpow_mod.hpp"



#line 5 "src\\code\\math\\qpow_mod.hpp"

namespace tifa_libs::math {

constexpr u64 qpow_mod(u64 a, u64 b, u64 mod) {
  u64 res(1);
  for (a %= mod; b; b >>= 1, a = mul_mod_u(a, a, mod))
    if (b & 1) res = mul_mod_u(res, a, mod);
  return res;
}

}  // namespace tifa_libs::math


#line 7 "src\\code\\math\\is_prime.hpp"

namespace tifa_libs::math {

constexpr bool is_prime(u64 n) {
  if (n <= 2) return n == 2;
  if (~n & 1) return false;
  if (n < 8) return true;
  constexpr u64 bases[12] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
  u64 d = (n - 1) >> bit::cntr0(n - 1);
  for (u64 i : bases) {
    if (n == i) return true;
    u64 t = d, y = qpow_mod(i, t, n);
    while (t != n - 1 && y != 1 && y != n - 1) {
      y = mul_mod_u(y, y, n);
      t <<= 1;
    }
    if (y != n - 1 && (~t & 1)) return false;
  }
  return true;
}

}  // namespace tifa_libs::math


#line 8 "src\\code\\math\\pfactors.hpp"

namespace tifa_libs::math {

namespace pfactors_detail__ {

class PollardRho {
  rand::Gen<std::uniform_int_distribution<u64>> e;

  u64 rho(u64 n) {
    e.set_range(2, n - 1);
    auto f = [n, r = e()](u64 x) { return (mul_mod_u(x, x, n) + r) % n; };
    u64 g = 1, x = 0, y = e(), yy = 0;
    const u32 LIM = 128;
    for (u64 r = 1, q = 1; g == 1; r *= 2) {
      x = y;
      for (u64 i = 0; i < r; ++i) y = f(y);
      for (u64 k = 0; g == 1 && k < r; k += LIM) {
        yy = y;
        for (u64 i = 0; i < LIM && i < r - k; ++i) q = mul_mod_u(q, (x + (n - (y = f(y)))) % n, n);
        g = std::gcd(q, n);
      }
    }
    if (g == n) do {
        g = std::gcd((x + (n - (yy = f(yy)))) % n, n);
      } while (g == 1);
    return g == n ? rho(n) : g;
  }

 public:
  explicit PollardRho() : e() {}

  void operator()(u64 n, std::map<u64, u32> &ans) {
    if (n < 2) return;
    if (is_prime(n)) {
      ++ans[n];
      return;
    }
    auto g = rho(n);
    (*this)(n / g, ans);
    (*this)(g, ans);
  }
};

}  // namespace pfactors_detail__

inline std::map<u64, u32> pfactors(u64 n) {
  std::map<u64, u32> ans;
  if (n < 2) return ans;
  if (~n & 1) n >>= (ans[2] = (u32)bit::cntr0(n));
  using pfactors_detail__::PollardRho;
  PollardRho()(n, ans);
  return ans;
}

}  // namespace tifa_libs::math


#line 1 "src\\code\\math\\proot_u32.hpp"



#line 1 "src\\code\\math\\isqrt.hpp"



#line 6 "src\\code\\math\\isqrt.hpp"

namespace tifa_libs::math {

constexpr u32 isqrt(u64 x) {
  int c = (bit::bwidth(x) - 1) / 2, sh = 31 - c;
  u32 u = [](u64 x) {
    constexpr uint8_t TAB[192] = {128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 144, 145, 146, 147, 148, 149, 150, 151, 151, 152, 153, 154, 155, 156, 156, 157, 158, 159, 160, 160, 161, 162, 163, 164, 164, 165, 166, 167, 167, 168, 169, 170, 170, 171, 172, 173, 173, 174, 175, 176, 176, 177, 178, 179, 179, 180, 181, 181, 182, 183, 183, 184, 185, 186, 186, 187, 188, 188, 189, 190, 190, 191, 192, 192, 193, 194, 194, 195, 196, 196, 197, 198, 198, 199, 200, 200, 201, 201, 202, 203, 203, 204, 205, 205, 206, 206, 207, 208, 208, 209, 210, 210, 211, 211, 212, 213, 213, 214, 214, 215, 216, 216, 217, 217, 218, 219, 219, 220, 220, 221, 221, 222, 223, 223, 224, 224, 225, 225, 226, 227, 227, 228, 228, 229, 229, 230, 230, 231, 232, 232, 233, 233, 234, 234, 235, 235, 236, 237, 237, 238, 238, 239, 239, 240, 240, 241, 241, 242, 242, 243, 243, 244, 244, 245, 246, 246, 247, 247, 248, 248, 249, 249, 250, 250, 251, 251, 252, 252, 253, 253, 254, 254, 255, 255, 255};
    u32 u = TAB[(x >> 56) - 64];
    u = (u << 7) + (u32)(x >> 41) / u;
    return (u << 15) + (u32)((x >> 17) / u);
  }(x << 2 * sh);
  u >>= sh;
  u -= (u64)u * u > x;
  return u;
}

}  // namespace tifa_libs::math


#line 7 "src\\code\\math\\proot_u32.hpp"

namespace tifa_libs::math {

constexpr u32 proot_u32(u32 m) {
  if (m == 2) return 1;
  if (m == 3 || m == 5) return 2;
  if (m == 104857601 || m == 167772161 || m == 469762049) return 3;
  if (m == 754974721) return 11;
  if (m == 998244353 || m == 1004535809) return 3;
  u32 divs[20] = {2};
  u32 cnt = 1, x = (m - 1) / 2;
  x >>= bit::cntr0(x);
  for (u32 i = 3, ed_ = isqrt(x); i <= ed_; i += 2)
    if (x % i == 0) {
      divs[cnt++] = i;
      while (x % i == 0) x /= i;
    }
  if (x > 1) divs[cnt++] = x;
  for (u32 g = 2;; ++g) {
    bool ok = true;
    for (u32 i = 0; i < cnt; ++i)
      if (qpow_mod(g, (m - 1) / divs[i], m) == 1) {
        ok = false;
        break;
      }
    if (ok) return g;
  }
}

}  // namespace tifa_libs::math


#line 7 "src\\code\\math\\proot_u64.hpp"

namespace tifa_libs::math {

inline u64 proot_u64(u64 m) {
  if (m <= (u32)(-1)) return proot_u32((u32)m);
  u64 r = 1;
  auto pf = pfactors(m - 1);
  while (true) {
    bool ok = 1;
    for (auto [q, k] : pf)
      if (qpow_mod(r, (m - 1) / q, m) == 1) {
        ok = 0;
        break;
      }
    if (ok) break;
    ++r;
  }
  return r;
}

}  // namespace tifa_libs::math


#line 1 "src\\code\\math\\qpow.hpp"



#line 5 "src\\code\\math\\qpow.hpp"

namespace tifa_libs::math {

template <class T>
constexpr T qpow(T a, u64 b) {
  T res(1);
  for (; b; b >>= 1, a *= a)
    if (b & 1) res *= a;
  return res;
}

}  // namespace tifa_libs::math


#line 8 "src\\code\\poly\\ntt.hpp"

namespace tifa_libs::math {

template <class mint>
struct NTT {
  static constexpr u64 MOD = mint::mod();
  static_assert((MOD & 3) == 1, "MOD must be prime with 4k+1");

  NTT() : root() {}

  size_t size() const { return root.size(); }
  void bzr(size_t len) {
    size_t n = bit::bceil(len);
    assert((MOD - 1) % n == 0);
    if (n == size()) return;
    root.resize(n);
    root[0] = 1;
    mint w = qpow(G, (MOD - 1) / n);
    for (size_t i = 1; i < n; ++i) root[i] = root[i - 1] * w;
  }

  void dif(vec<mint> &f) const {
    size_t n = size();
    assert(f.size() <= n);
    f.resize(n);
    for (size_t i = n / 2, d = 1; i; i /= 2, d *= 2)
      for (size_t j = 0; j < n; j += i * 2) {
        auto w = root.begin();
        mint u, t;
        for (size_t k = 0; k < i; ++k, w += d) {
          f[j | k] = (u = f[j | k]) + (t = f[i | j | k]);
          f[i | j | k] = (u - t) * (*w);
        }
      }
  }
  void dit(vec<mint> &f) const {
    size_t n = size();
    assert(f.size() <= n);
    f.resize(n);
    for (size_t i = 1, d = n / 2; d; i *= 2, d /= 2)
      for (size_t j = 0; j < n; j += i * 2) {
        auto w = root.begin();
        mint t;
        for (size_t k = 0; k < i; ++k, w += d) {
          f[i | j | k] = f[j | k] - (t = f[i | j | k] * (*w));
          f[j | k] += t;
        }
      }
    std::reverse(f.begin() + 1, f.end());
    mint t = mint(n).inv();
    for (size_t i = 0; i < n; ++i) f[i] *= t;
  }

 private:
  const mint G = proot_u64(MOD);

  vec<mint> root;
};

}  // namespace tifa_libs::math


#line 6 "src\\code\\poly\\conv_ntt.hpp"

namespace tifa_libs::math {

template <class mint>
inline vec<mint> conv_ntt(vec<mint> l, vec<mint> r, size_t ans_size) {
  static NTT<mint> ntt;
  ntt.bzr(std::min(l.size() + r.size() - 1, ans_size));
  ntt.dif(l);
  ntt.dif(r);
  for (size_t i = 0; i < ntt.size(); ++i) l[i] *= r[i];
  ntt.dit(l);
  l.resize(ans_size);
  return l;
}
template <class mint>
inline vec<mint> conv_ntt(vec<mint> const &l, vec<mint> const &r) { return conv_ntt(l, r, l.size() + r.size() - 1); }

template <class mint>
inline vec<mint> conv_ntt(vec<u64> const &l, vec<u64> const &r, size_t ans_size) {
  vec<mint> l_, r_;
  l_.reserve(l.size());
  r_.reserve(r.size());
  for (auto i : l) l_.push_back(i);
  for (auto i : r) r_.push_back(i);
  return conv_ntt(l_, r_, ans_size);
}
template <class mint>
inline vec<mint> conv_ntt(vec<u64> const &l, vec<u64> const &r) { return conv_ntt(l, r, l.size() + r.size() - 1); }

}  // namespace tifa_libs::math


#line 7 "src\\code\\poly\\polydata_s.hpp"

namespace tifa_libs::math {

template <class mint>
struct polydata_s {
  static constexpr u64 MOD = mint::mod();
  static_assert(MOD > 1 && (MOD & 3) == 1, "MOD must be prime with 4k+1");

  using value_type = mint;

  vec<mint> d;

  explicit constexpr polydata_s(size_t sz = 1) : d(std::max((size_t)1, sz)) {}
  explicit constexpr polydata_s(std::initializer_list<mint> v) : d(v) {}
  explicit constexpr polydata_s(vec<mint> const &v) : d(v) {}

  void conv(polydata_s const &r, size_t ans_size) { d = ans_size < 32 ? conv_naive(d, r.d, ans_size) : conv_ntt(d, r.d, ans_size); }
  void conv(polydata_s const &r) { conv(r, d.size() + r.d.size() - 1); }
};

}  // namespace tifa_libs::math


#line 6 "src\\test_cpverifier\\yukicoder\\0963.0.test.cpp"

using mint = tifa_libs::math::mint_s30<1012924417>;
using pldt_t = tifa_libs::math::polydata_s<mint>;
using poly_t = tifa_libs::math::poly<pldt_t>;

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  size_t n;
  std::cin >> n;
  auto g = [](poly_t const& f, size_t n) { return ((f * f + 1) * mint(2).inv()).pre(n); };
  auto dg = [](poly_t const& f, size_t n) { return f.pre(n); };
  mint ans = tifa_libs::math::poly_ode<pldt_t>(g, dg, 1, n + 1)[n] * 2;
  for (size_t i = 2; i <= n; ++i) ans *= i;
  std::cout << ans;
  return 0;
}