#ifndef M_MODINT_H
#define M_MODINT_H

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>

#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wsign-compare"
#if __cplusplus < 201700L
#pragma GCC diagnostic ignored "-Wc++17-extensions"
#warning "Some features may not be available under c++17."
#endif

#define _static_helper __attribute__((always_inline)) constexpr inline static
#define _set_op(tp, op, attr)                                                  \
  attr tp operator op(const tp &rhs) const {                                   \
    tp lhs = *this;                                                            \
    return lhs op## = rhs;                                                     \
  }

// === BEGIN Modint library ===

namespace Moeebius {

template <std::uint32_t mod> class Modint {
  using i32 = std::int32_t;
  using u32 = std::uint32_t;
  using i64 = std::int64_t;
  using u64 = std::uint64_t;

  u32 _v;
  _static_helper u32 __get_inv_r(u32 x) {
    u32 y = x;
    y *= 2ull - x * y, y *= 2ull - x * y, y *= 2ull - x * y, y *= 2ull - x * y;
    return y;
  }
  _static_helper u32 __shrk(u32 x) { return std::min(x, x - mod); }
  _static_helper u32 __shrk2(u32 x) { return std::min(x, x - 2 * mod); }
  _static_helper u32 __dilt2(u32 x) { return std::min(x, x + 2 * mod); }
  _static_helper u32 __reduce(u64 x) {
    return (x + u64(u32(x) * -mod_inv) * mod) >> 32;
  }

  constexpr static inline u32 r2 = (1ull << 32) % mod * (1ull << 32) % mod,
                              mod_inv = __get_inv_r(mod);
  static_assert(mod && (mod < (1u << 30)) && (mod & 1) &&
                (mod_inv * mod) == 1u && __reduce(r2) == (1ull << 32) % mod);

public:
  constexpr Modint() : _v(0) {}
  constexpr Modint(u32 v) : _v(__reduce(u64(v) * r2)) {}
  constexpr Modint(i32 v) : _v(__reduce(u64(__dilt2(v % i32(mod))) * r2)) {}
  // constexpr Modint(u64 v) : _v(__reduce(u64(v % mod) * r2)) {}
  // constexpr Modint(i64 v) : _v(__reduce(u64((v % mod + mod) % mod) * r2)) {}
  // NOTE: `int64_t` maybe `long` or `long long`.
  constexpr Modint(long v) : _v(__reduce(u64((v % mod + mod) % mod) * r2)) {}
  constexpr Modint(long long v)
      : _v(__reduce(u64((v % mod + mod) % mod) * r2)) {}
  constexpr Modint operator-() const { return Modint() - *this; }
  constexpr Modint &operator+=(Modint rhs) {
    return _v = __shrk2(_v + rhs._v), *this;
  }
  constexpr Modint &operator-=(Modint rhs) {
    return _v = __dilt2(_v - rhs._v), *this;
  }
  constexpr Modint &operator*=(Modint rhs) {
    return _v = __reduce(u64(_v) * rhs._v), *this;
  }
  constexpr Modint pow(u64 y) const {
    Modint ans = 1, x = *this;
    while (y) {
      if (y & 1)
        ans *= x;
      x *= x, y >>= 1;
    }
    return ans;
  }
  constexpr Modint inv() const { return this->pow(mod - 2); }
  constexpr u32 val() const { return __shrk(__reduce(_v)); }
  constexpr Modint &operator/=(Modint rhs) { return (*this) *= rhs.inv(); }
  constexpr explicit operator bool() const { return __shrk(_v); }
  constexpr bool operator==(const Modint &rhs) const {
    return __shrk(_v) == __shrk(rhs._v);
  }
  constexpr bool operator!=(const Modint &rhs) const {
    return __shrk(_v) != __shrk(rhs._v);
  }
  _set_op(Modint, +, constexpr);
  _set_op(Modint, -, constexpr);
  _set_op(Modint, *, constexpr);
  _set_op(Modint, /, constexpr);
};

template <uint32_t mod>
std::istream &operator>>(std::istream &x, Modint<mod> &y) {
  int32_t _v;
  return x >> _v, y = _v, x;
}
template <uint32_t mod>
std::ostream &operator<<(std::ostream &x, Modint<mod> y) {
  return x << y.val();
}

} // namespace Moeebius

// === END Modint library ===

#undef _static_helper
#undef _set_op

#pragma GCC diagnostic pop

#endif

#ifndef M_FAST_INV_H
#define M_FAST_INV_H

#include <cstdint>
#include <iostream>

#pragma GCC diagnostic push
#if __cplusplus < 201700L
#pragma GCC diagnostic ignored "-Wc++17-extensions"
#warning "Some features may not be available under c++17."
#endif

namespace Moeebius {

template <std::int32_t mod> class FastInv {
  static_assert(mod > (1 << 25) && mod < (1 << 30));
  using Z = Modint<mod>;
  constexpr static inline int B = 1 << 10, N = (1 << 21) + 1, lim1 = mod >> 10,
                              lim2 = mod - lim1;
  static inline bool ok = false;
  static inline int u[N], v[N];
  static inline Z _inv[N << 1], *inv = _inv + N;
  static inline void init() {
    ok = true;
    for (int i = 1; i <= B; i++) {
      int d = i << 10;
      for (int j = 0, k = 0; k <= lim1; (j += d) >= mod ? j -= mod : 0, k++) {
        // std::cerr << i << ' ' << j << ' ' << k << '\n';
        assert(j == ((long long)(i)*k % mod << 10) % mod);
        if (j <= lim1)
          u[k] = i;
        else if (j >= lim2)
          u[k] = -i;
        else {
          int dlt = (lim2 - j - 1) / d;
          j += dlt * d, k += dlt;
        }
      }
    }
    for (int i = 1; i <= lim1; i++) {
      v[i] = (long long)(i << 10) * (u[i] + mod) % mod;
      if (__builtin_expect(v[i] >= lim2, 0))
        v[i] -= mod;
    }
    inv[1] = 1;
    for (int i = 2; i <= lim1 * 2; i++)
      inv[i] = inv[mod % i] * (-Z(mod / i));
    for (int i = 1; i <= lim1 * 2; i++)
      inv[-i] = -inv[i];
  }

public:
  static inline Z get_inv(Z _x) {
    if (__builtin_expect(!ok, 0))
      init();
    int x = _x.val();
    assert(x);
    if (x <= lim1)
      return inv[x];
    int a = x >> 10, c = x & 1023, uu = u[a];
    return inv[v[a] + c * uu] * uu;
  }
};

} // namespace Moeebius

#pragma GCC diagnostic pop

#endif

#include "inv.h"

using Z = Moeebius::Modint<998244353>;
using fast_inv = Moeebius::FastInv<998244353>;

void init(int p) {}

int inv(int x) { return fast_inv::get_inv(Z(x)).val(); }