#pragma region template
// clang-format off

#if __has_include(<src.hpp>)
#include <src.hpp>  // precompiled header
#endif

#if (defined __INTELLISENSE__) && (!defined PROPER)
#define NDEBUG
namespace std {
#endif

#include <cassert>
#include <cctype>
#include <cmath>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <iomanip>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

#if (defined __INTELLISENSE__) && (!defined PROPER)
  using namespace std;
}
#endif

#ifdef LOCAL_DEBUG
#include <debugger.hpp>  // https://gist.github.com/naskya/2c5c84dbc8f70a2e5680b4267fff1af5
#define see(...) debugger::print(#__VA_ARGS__, __VA_ARGS__)
#define here(label) debugger::output << "[Debug] " << #label << (std::string(#label).empty() ? "" : " | ") << "line " << __LINE__ << " (" << __func__ << ")\n"
#define reveal(...) do {here(); see(__VA_ARGS__);} while(0)
#define com(msg) debugger::output << "[Debug] " << msg << "\n"
#define local(x) do {x} while(0)
#define alter(x, y) x
#else
#define see(...) (static_cast<void>(0))
#define here(label) (static_cast<void>(0))
#define reveal(...) (static_cast<void>(0))
#define com(msg) (static_cast<void>(0))
#define local(x) (static_cast<void>(0))
#define alter(x, y) y
#endif

#if (!defined LOCAL_DEBUG) || (defined NOWARN)
#define warn(msg) (static_cast<void>(0))
#else
#define warn(msg) debugger::output << "[Warning] " << msg << "\n"
#endif

#if (defined LOCAL_DEBUG) || (defined LOCAL_NDEBUG) || (defined __INTELLISENSE__)
#define NOEXCEPT
#define M_assert(expr) assert(expr)
#define O_assert(expr) assert(expr)
#else
#define NOEXCEPT noexcept
#define M_assert(expr) do {if(__builtin_expect(!(expr), 0)) {long long *p = (long long*) std::malloc(1 << 30); for (int i = 0; i < static_cast<int>((1 << 30) / sizeof(long long)); p[i] = 1, i += (1 << 9)); std::fprintf(stderr, "%lld", *p);}} while(0)
#define O_assert(expr) do {if(__builtin_expect(!(expr), 0)) for(int i = 0; i < (1 << 24); i++) std::puts("Hello, world!");} while(0)
#endif

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rng(i, f, t, s) for (int i = (f); ((s) > 0) ? (i < (int)(t)) : (i > (int)(t)); i += (s))
#define erng(i, f, t, s) for (int i = (f); ((s) > 0) ? (i <= (int)(t)) : (i >= (int)(t)); i += (s))

[[maybe_unused]] constexpr int         INF   = 1000000005;
[[maybe_unused]] constexpr long long   LINF  = 1000000000000000005LL;
[[maybe_unused]] constexpr double      EPS   = 1e-9;
[[maybe_unused]] constexpr long double LEPS  = 1e-14L;
[[maybe_unused]] constexpr int         dy[9] = {1, 0, -1, 0, 1, 1, -1, -1, 0};
[[maybe_unused]] constexpr int         dx[9] = {0, 1, 0, -1, -1, 1, 1, -1, 0};

template <class S, class T, class... U, class V = std::common_type_t<S, T, U...>> constexpr V Min(const S a, const T b, const U... c) {
  if constexpr (sizeof...(U)) return std::min((V) a, (V) Min(b, c...)); else return std::min((V) a, (V) b);
}
template <class S, class T, class... U, class V = std::common_type_t<S, T, U...>> constexpr V Max(const S a, const T b, const U... c) {
  if constexpr (sizeof...(U)) return std::max((V) a, (V) Max(b, c...)); else return std::max((V) a, (V) b);
}

// clang-format on
#pragma endregion

constexpr int MOD = 998244353;

#pragma region lib_static_modint

#ifndef lib_mint
#define lib_mint 1
#define lib_static_modint 1

namespace lib {
  template <int modulo> class static_modint {
    int value;
    template <class Tp> static constexpr int calc_inverse(Tp n) noexcept {
      Tp b = modulo, u = 1, v = 0, t = 0;
      while (b > 0) {
        t = n / b;
        // std::swap is not necessarily constexpr in C++17
        // std::swap(n -= t * b, b);
        Tp tmp = std::move(n -= t * b);
        n      = std::move(b);
        b      = std::move(tmp);
        // std::swap(u -= t * v, v);
        tmp = std::move(u -= t * v);
        u   = std::move(v);
        v   = std::move(tmp);
      }
      return static_cast<int>(u);
    }

    template <class Tp> static constexpr int clamp_ll(Tp v) noexcept {
      if (modulo <= v || v < -modulo) v %= modulo;
      if (v < 0) v += modulo;
      return static_cast<int>(v);
    }

    constexpr void clamp_self(void) noexcept {
      if (0 <= value) {
        if (value < modulo) return;
        if (value < modulo * 2)
          value -= modulo;
        else
          value -= modulo * 2;
      } else {
        if (-modulo < value)
          value += modulo;
        else if (-modulo * 2 < value)
          value += modulo * 2;
        else {
          value += modulo;
          value += modulo * 2;
        }
      }
    }

    public:
    // constructor
    constexpr static_modint(void) noexcept : value(0) {}
    template <class Valuetype> constexpr static_modint(const Valuetype v) noexcept {
      if constexpr (std::is_same_v<Valuetype, int>) {
        value = v;
        clamp_self();
      } else {
        value = clamp_ll(v);
      }
    }
    constexpr static_modint(const int v, bool) noexcept : value(v) {}

    // operator
    constexpr static_modint<modulo> operator+(const static_modint<modulo> rhs) const noexcept {
      return static_modint<modulo>(value + rhs.value);
    }
    constexpr static_modint<modulo> operator-(const static_modint<modulo> rhs) const noexcept {
      return static_modint<modulo>(value - rhs.value);
    }
    constexpr static_modint<modulo> operator*(const static_modint<modulo> rhs) const noexcept {
      return static_modint<modulo>(static_cast<long long>(value) * rhs.value);
    }
    constexpr static_modint<modulo> operator/(const static_modint<modulo> rhs) const NOEXCEPT {
      O_assert(rhs.value != 0);
      return static_modint<modulo>(static_cast<long long>(value) * calc_inverse(rhs.value));
    }

    constexpr static_modint<modulo> operator%(const static_modint<modulo> rhs) const NOEXCEPT {
      warn("static_modint::operator% : Are you sure you want to do this?");
      O_assert(rhs.value != 0);
      return static_modint<modulo>(value % rhs.value, true);
    }

    constexpr static_modint<modulo> operator&(const static_modint<modulo> rhs) const noexcept {
      warn("static_modint::operator& : Are you sure you want to do this?");
      return static_modint<modulo>(value & rhs.value, true);
    }
    constexpr static_modint<modulo> operator|(const static_modint<modulo> rhs) const noexcept {
      warn("static_modint::operator| : Are you sure you want to do this?");
      return static_modint<modulo>(value | rhs.value);
    }
    constexpr static_modint<modulo> operator^(const static_modint<modulo> rhs) const noexcept {
      warn("static_modint::operator^ : Are you sure you want to do this?");
      return static_modint<modulo>(value ^ rhs.value);
    }
    constexpr static_modint<modulo> operator<<(const static_modint<modulo> rhs) const noexcept {
      warn("static_modint::operator<< : Are you sure you want to do this?");
      return static_modint<modulo>(static_cast<long long>(value) << rhs.value);
    }
    constexpr static_modint<modulo> operator>>(const static_modint<modulo> rhs) const noexcept {
      warn("static_modint::operator>> : Are you sure you want to do this?");
      return static_modint<modulo>(value >> rhs.value, true);
    }

    constexpr static_modint<modulo>& operator+=(const static_modint<modulo> rhs) noexcept {
      value += rhs.value;
      if (value >= modulo) value -= modulo;
      return *this;
    }
    constexpr static_modint<modulo>& operator-=(const static_modint<modulo> rhs) noexcept {
      value -= rhs.value;
      if (value < 0) value += modulo;
      return *this;
    }
    constexpr static_modint<modulo>& operator*=(const static_modint<modulo> rhs) noexcept {
      value = clamp_ll(static_cast<long long>(value) * rhs.value);
      return *this;
    }
    constexpr static_modint<modulo>& operator/=(const static_modint<modulo> rhs) NOEXCEPT {
      O_assert(rhs != 0);
      value = clamp_ll(static_cast<long long>(value) * calc_inverse(rhs.value));
      return *this;
    }

    constexpr static_modint<modulo>& operator%=(const static_modint<modulo> rhs) NOEXCEPT {
      warn("static_modint::operator%= : Are you sure you want to do this?");
      O_assert(rhs != 0);
      value %= rhs.value;
      if (value < 0) value += modulo;
      return *this;
    }

    constexpr static_modint<modulo>& operator&=(const static_modint<modulo> rhs) noexcept {
      warn("static_modint::operator&= : Are you sure you want to do this?");
      value &= rhs.value;
      return *this;
    }
    constexpr static_modint<modulo>& operator|=(const static_modint<modulo> rhs) noexcept {
      warn("static_modint::operator|= : Are you sure you want to do this?");
      value |= rhs.value;
      clamp_self();
      return *this;
    }
    constexpr static_modint<modulo>& operator^=(const static_modint<modulo> rhs) noexcept {
      warn("static_modint::operator^= : Are you sure you want to do this?");
      value ^= rhs.value;
      clamp_self();
      return *this;
    }
    constexpr static_modint<modulo>& operator<<=(const static_modint<modulo> rhs) noexcept {
      warn("static_modint::operator<<= : Are you sure you want to do this?");
      value = clamp_ll(static_cast<long long>(value) << rhs.value);
      return *this;
    }
    constexpr static_modint<modulo>& operator>>=(const static_modint<modulo> rhs) noexcept {
      warn("static_modint::operator>>= : Are you sure you want to do this?");
      value >>= rhs.value;
      return *this;
    }

    template <class RhsType> constexpr static_modint<modulo> operator+(const RhsType rhs) const noexcept {
      return static_modint<modulo>(static_cast<long long>(value) + rhs);
    }
    template <class RhsType> constexpr static_modint<modulo> operator-(const RhsType rhs) const noexcept {
      return static_modint<modulo>(static_cast<long long>(value) - rhs);
    }
    template <class RhsType> constexpr static_modint<modulo> operator*(const RhsType rhs) const noexcept {
      return static_modint<modulo>(static_cast<long long>(value) * rhs);
    }
    template <class RhsType> constexpr static_modint<modulo> operator/(const RhsType rhs) const NOEXCEPT {
      O_assert(rhs != 0);
      long long mul = (rhs > 0) ? calc_inverse(rhs) : -calc_inverse(-rhs);
      return static_modint<modulo>(mul * value);
    }

    template <class RhsType> constexpr static_modint<modulo> operator%(const RhsType rhs) const NOEXCEPT {
      warn("static_modint::operator% : Are you sure you want to do this?");
      O_assert(rhs != 0);
      return static_modint<modulo>(value % rhs, true);
    }

    template <class RhsType> constexpr static_modint<modulo> operator&(const RhsType rhs) const noexcept {
      warn("static_modint::operator& : Are you sure you want to do this?");
      return static_modint<modulo>(value & rhs, true);
    }
    template <class RhsType> constexpr static_modint<modulo> operator|(const RhsType rhs) const noexcept {
      warn("static_modint::operator| : Are you sure you want to do this?");
      return static_modint<modulo>(value | rhs);
    }
    template <class RhsType> constexpr static_modint<modulo> operator^(const RhsType rhs) const noexcept {
      warn("static_modint::operator^ : Are you sure you want to do this?");
      return static_modint<modulo>(value ^ rhs);
    }
    template <class RhsType> constexpr static_modint<modulo> operator<<(const RhsType rhs) const noexcept {
      warn("static_modint::operator<< : Are you sure you want to do this?");
      return static_modint<modulo>(static_cast<long long>(value) << rhs);
    }
    template <class RhsType> constexpr static_modint<modulo> operator>>(const RhsType rhs) const noexcept {
      warn("static_modint::operator>> : Are you sure you want to do this?");
      return static_modint<modulo>(value >> rhs, true);
    }

    template <class RhsType> constexpr static_modint<modulo>& operator+=(const RhsType rhs) noexcept {
      value = clamp_ll(static_cast<long long>(value) + rhs);
      return *this;
    }
    template <class RhsType> constexpr static_modint<modulo>& operator-=(const RhsType rhs) noexcept {
      value = clamp_ll(static_cast<long long>(value) - rhs);
      return *this;
    }
    template <class RhsType> constexpr static_modint<modulo>& operator*=(const RhsType rhs) noexcept {
      value = clamp_ll(static_cast<long long>(value) * rhs);
      return *this;
    }
    template <class RhsType> constexpr static_modint<modulo>& operator/=(const RhsType rhs) NOEXCEPT {
      O_assert(rhs != 0);
      long long mul = (rhs > 0) ? calc_inverse(rhs) : -calc_inverse(-rhs);
      value         = clamp_ll(mul * value);
      return *this;
    }

    template <class RhsType> constexpr static_modint<modulo>& operator%=(const RhsType rhs) NOEXCEPT {
      warn("static_modint::operator%= : Are you sure you want to do this?");
      O_assert(rhs != 0);
      value %= rhs;
      return *this;
    }

    template <class RhsType> constexpr static_modint<modulo>& operator&=(const RhsType rhs) noexcept {
      warn("static_modint::operator&= : Are you sure you want to do this?");
      value &= rhs;
      return *this;
    }
    template <class RhsType> constexpr static_modint<modulo>& operator|=(const RhsType rhs) noexcept {
      warn("static_modint::operator|= : Are you sure you want to do this?");
      value |= rhs;
      clamp_self();
      return *this;
    }
    template <class RhsType> constexpr static_modint<modulo>& operator^=(const RhsType rhs) noexcept {
      warn("static_modint::operator^= : Are you sure you want to do this?");
      value ^= rhs;
      clamp_self();
      return *this;
    }
    template <class RhsType> constexpr static_modint<modulo>& operator<<=(const RhsType rhs) noexcept {
      warn("static_modint::operator<<= : Are you sure you want to do this?");
      value = clamp_ll(static_cast<long long>(value) << rhs);
      return *this;
    }
    template <class RhsType> constexpr static_modint<modulo>& operator>>=(const RhsType rhs) noexcept {
      warn("static_modint::operator>>= : Are you sure you want to do this?");
      value >>= rhs;
      return *this;
    }

    constexpr bool operator!(void) const noexcept {
      warn("static_modint::operator! : Are you sure you want to do this?");
      return value == 0;
    }
    constexpr static_modint<modulo> operator~(void) const noexcept {
      warn("static_modint::operator~ : Are you sure you want to do this?");
      return static_modint<modulo>(~value);
    }
    constexpr static_modint<modulo> operator-(void) const noexcept {
      return static_modint<modulo>(value == 0 ? 0 : modulo - value, true);
    }
    constexpr static_modint<modulo> operator+(void) const noexcept {
      return *this;
    }

    constexpr static_modint<modulo>& operator++(void) noexcept {
      value = ((value + 1 == modulo) ? 0 : value + 1);
      return *this;
    }
    constexpr static_modint<modulo>& operator--(void) noexcept {
      value = ((value == 0) ? modulo - 1 : value - 1);
      return *this;
    }
    constexpr static_modint<modulo> operator++(int) noexcept {
      int ret = value;
      ++(*this);
      return static_modint<modulo>(ret, true);
    }
    constexpr static_modint<modulo> operator--(int) noexcept {
      int ret = value;
      --(*this);
      return static_modint<modulo>(ret, true);
    }

    constexpr bool operator==(const static_modint<modulo> rhs) const noexcept {
      return value == rhs.value;
    }
    constexpr bool operator!=(const static_modint<modulo> rhs) const noexcept {
      return value != rhs.value;
    }
    constexpr bool operator<(const static_modint<modulo> rhs) const noexcept {
      warn("static_modint::operator< : Are you sure you want to do this?");
      return value < rhs.value;
    }
    constexpr bool operator<=(const static_modint<modulo> rhs) const noexcept {
      warn("static_modint::operator<= : Are you sure you want to do this?");
      return value <= rhs.value;
    }
    constexpr bool operator>(const static_modint<modulo> rhs) const noexcept {
      warn("static_modint::operator> : Are you sure you want to do this?");
      return value > rhs.value;
    }
    constexpr bool operator>=(const static_modint<modulo> rhs) const noexcept {
      warn("static_modint::operator>= : Are you sure you want to do this?");
      return value >= rhs.value;
    }
    constexpr bool operator&&(const static_modint<modulo> rhs) const noexcept {
      warn("static_modint::operator&& : Are you sure you want to do this?");
      return value && rhs.value;
    }
    constexpr bool operator||(const static_modint<modulo> rhs) const noexcept {
      warn("static_modint::operator|| : Are you sure you want to do this?");
      return value || rhs.value;
    }

    template <class RhsType> constexpr bool operator==(const RhsType rhs) const noexcept {
      return value == rhs;
    }
    template <class RhsType> constexpr bool operator!=(const RhsType rhs) const noexcept {
      return value != rhs;
    }
    template <class RhsType> constexpr bool operator<(const RhsType rhs) const noexcept {
      warn("static_modint::operator< : Are you sure you want to do this?");
      return value < rhs;
    }
    template <class RhsType> constexpr bool operator<=(const RhsType rhs) const noexcept {
      warn("static_modint::operator<= : Are you sure you want to do this?");
      return value <= rhs;
    }
    template <class RhsType> constexpr bool operator>(const RhsType rhs) const noexcept {
      warn("static_modint::operator> : Are you sure you want to do this?");
      return value > rhs;
    }
    template <class RhsType> constexpr bool operator>=(const RhsType rhs) const noexcept {
      warn("static_modint::operator>= : Are you sure you want to do this?");
      return value >= rhs;
    }
    template <class RhsType> constexpr bool operator&&(const RhsType rhs) const noexcept {
      warn("static_modint::operator&& : Are you sure you want to do this?");
      return value && rhs;
    }
    template <class RhsType> constexpr bool operator||(const RhsType rhs) const noexcept {
      warn("static_modint::operator|| : Are you sure you want to do this?");
      return value || rhs;
    }

    constexpr operator int() const noexcept {
      return value;
    }

    friend std::istream& operator>>(std::istream& is, static_modint<modulo>& rhs) {
      long long tmp;
      is >> tmp;
      if (tmp < -modulo || modulo <= tmp) tmp %= modulo;
      if (tmp < 0) tmp += modulo;
      rhs.value = static_cast<int>(tmp);
      return is;
    }
    friend std::ostream& operator<<(std::ostream& os, static_modint<modulo>& rhs) {
      return os << rhs.value;
    }

    // functions
    constexpr static_modint<modulo> inv(void) const NOEXCEPT {
      O_assert(value != 0);
      return static_modint<modulo>(calc_inverse(value), true);
    }
    template <bool index_positive_guaranteed = true, class Tp = int>
    constexpr static_modint<modulo> pow(Tp index) const noexcept {
      if constexpr (!index_positive_guaranteed) {
        O_assert(value != 0 || index > 0);
        if (value == 0) return static_modint<modulo>(0, true);
        if (index == 0) return static_modint<modulo>(1, true);
        if (index < 0) return static_modint<modulo>(value, true).inv().pow(-index);
      }
      static_modint<modulo> ret(1, true), base(value, true);
      while (index > 0) {
        if (index & 1) ret *= base;
        base *= base;
        index >>= 1;
      }
      return ret;
    }
    constexpr std::pair<int, int> to_frac(void) const noexcept {
      int x = modulo - value, y = value, u = 1, v = 1;
      std::pair<int, int> ret{value, 1};

      int num = value, den = 1;
      int cost = num + den;

      while (x > 0) {
        if (x <= num) {
          int q = num / x;
          num   = num % x;
          den += q * u;
          if (num == 0) break;
          if (num + den < cost) {
            cost      = num + den;
            ret.first = num, ret.second = den;
          }
        }
        int q = y / x;
        y     = y % x;
        v += q * u;
        q = x / y;
        x = x % y;
        u += q * v;
      }

      return ret;
    }
  };

  template <class LhsType, int modulo>
  constexpr static_modint<modulo> operator+(const LhsType lhs, const static_modint<modulo> rhs) noexcept {
    return rhs + lhs;
  }
  template <class LhsType, int modulo>
  constexpr static_modint<modulo> operator-(const LhsType lhs, const static_modint<modulo> rhs) noexcept {
    return -rhs + lhs;
  }
  template <class LhsType, int modulo>
  constexpr static_modint<modulo> operator*(const LhsType lhs, const static_modint<modulo> rhs) noexcept {
    return rhs * lhs;
  }
  template <class LhsType, int modulo>
  constexpr static_modint<modulo> operator/(const LhsType lhs, const static_modint<modulo> rhs) noexcept {
    return rhs.inv() * lhs;
  }

  template <class LhsType, int modulo>
  constexpr static_modint<modulo> operator%(const LhsType lhs, const static_modint<modulo> rhs) noexcept {
    warn("operator%<LhsType, static_modint> : Are you sure you want to do this?");
    return static_modint<modulo>(lhs % (int) rhs, true);
  }

  template <class LhsType, int modulo, std::enable_if_t<std::is_integral_v<LhsType>, std::nullptr_t> = nullptr>
  constexpr static_modint<modulo> operator<<(const LhsType lhs, const static_modint<modulo> rhs) noexcept {
    warn("operator<< <LhsType, static_modint> : Are you sure you want to do this?");
    return static_modint<modulo>(static_cast<long long>(lhs) << (int) rhs);
  }
  template <class LhsType, int modulo, std::enable_if_t<std::is_integral_v<LhsType>, std::nullptr_t> = nullptr>
  constexpr static_modint<modulo> operator>>(const LhsType lhs, const static_modint<modulo> rhs) noexcept {
    warn("operator>> <LhsType, static_modint> : Are you sure you want to do this?");
    return static_modint<modulo>(lhs >> (int) rhs);
  }

  template <class LhsType, int modulo>
  constexpr LhsType& operator+=(LhsType& lhs, const static_modint<modulo> rhs) noexcept {
    return lhs += (int) rhs;
  }
  template <class LhsType, int modulo>
  constexpr LhsType& operator-=(LhsType& lhs, const static_modint<modulo> rhs) noexcept {
    return lhs -= (int) rhs;
  }
  template <class LhsType, int modulo>
  constexpr LhsType& operator*=(LhsType& lhs, const static_modint<modulo> rhs) noexcept {
    return lhs *= (int) rhs;
  }
  template <class LhsType, int modulo>
  constexpr LhsType& operator/=(LhsType& lhs, const static_modint<modulo> rhs) noexcept {
    return lhs /= (int) rhs;
  }

  template <class LhsType, int modulo>
  constexpr LhsType& operator%=(LhsType& lhs, const static_modint<modulo> rhs) noexcept {
    warn("operator%= <LhsType, static_modint> : Are you sure you want to do this?");
    return lhs %= (int) rhs;
  }

  template <class LhsType, int modulo>
  constexpr LhsType& operator&=(LhsType& lhs, const static_modint<modulo> rhs) noexcept {
    warn("operator&= <LhsType, static_modint> : Are you sure you want to do this?");
    return lhs &= (int) rhs;
  }
  template <class LhsType, int modulo>
  constexpr LhsType& operator|=(LhsType& lhs, const static_modint<modulo> rhs) noexcept {
    warn("operator|= <LhsType, static_modint> : Are you sure you want to do this?");
    return lhs |= (int) rhs;
  }
  template <class LhsType, int modulo>
  constexpr LhsType& operator^=(LhsType& lhs, const static_modint<modulo> rhs) noexcept {
    warn("operator^= <LhsType, static_modint> : Are you sure you want to do this?");
    return lhs ^= (int) rhs;
  }
  template <class LhsType, int modulo>
  constexpr LhsType& operator<<=(LhsType& lhs, const static_modint<modulo> rhs) noexcept {
    warn("operator<<= <LhsType, static_modint> : Are you sure you want to do this?");
    return lhs <<= (int) rhs;
  }
  template <class LhsType, int modulo>
  constexpr LhsType& operator>>=(LhsType& lhs, const static_modint<modulo> rhs) noexcept {
    warn("operator>>= <LhsType, static_modint> : Are you sure you want to do this?");
    return lhs >>= (int) rhs;
  }
}  // namespace lib
using mint = lib::static_modint<MOD>;
template <int modulo, class Tp>
struct std::common_type<lib::static_modint<modulo>, Tp> { using type = mint; };
template <int modulo, class Tp>
struct std::common_type<Tp, lib::static_modint<modulo>> { using type = mint; };
template <int modulo>
struct std::common_type<lib::static_modint<modulo>, lib::static_modint<modulo>> { using type = lib::static_modint<modulo>; };
#endif

#pragma endregion

#pragma region lib_prime_number

namespace lib {
  // Function to determine if the given value is a prime number
  // usage: is_prime(1), is_prime(1000)
  // output: true or false
  // time complexity: O(sqrt n)
  template <class T> bool is_prime(T n) {
    if (n <= 1) return false;
    T i = 2;
    while (i * i <= n) {
      if (n % i == 0 && n != i) return false;
      ++i;
    }
    return true;
  }

  template <class T> int min_divisor(T n) {
    int i = 2;
    while (i * i <= n) {
      if (n % i == 0 && n != i) return i;
      ++i;
    }
    return n;
  }

  // Function that returns the n-th prime number (0-indexed, prime(0) = 2)
  // This function returns -1 if the n-th prime number is grater than max_
  // usage: prime(3, 100)
  // time complexity: O(n log log n)
  template <int max_ = 10000000> int prime(int idx) {
    O_assert(idx >= 0);
    constexpr int sq_max = static_cast<int>(std::sqrt(max_));
    std::vector<signed char> sieve(max_ + 1);
    int cnt = 0, i = 2;
    for (; i <= sq_max; ++i) {
      if (!sieve[i]) {
        if (++cnt == idx) return i;
        for (int j = i * i; j <= max_; j += i)
          sieve[j] = true;
      }
    }

    for (; i <= max_; ++i) {
      if (!sieve[i] && (++cnt == idx)) return i;
    }
    return -1;
  }

  template <int max_ = 10000000> constexpr std::vector<int> primes_seq_of_length(int length) {
    O_assert(length >= 0);
    std::vector<int> ret(length);
    O_assert(length >= 0);
    constexpr int sq_max = static_cast<int>(std::sqrt(max_));
    std::vector<signed char> sieve(max_ + 1);
    int cnt = 0, i = 2;
    for (; i <= sq_max; ++i) {
      if (!sieve[i]) {
        ret[cnt++] = i;
        if (cnt == length) return ret;
        for (int j = i * i; j <= max_; j += i)
          sieve[j] = true;
      }
    }

    for (; i <= max_; ++i) {
      if (!sieve[i]) {
        ret[cnt++] = i;
        if (cnt == length) return ret;
      }
    }

    return ret;
  }

  std::vector<int> primes_seq_under(int max_) {
    int sq_max = static_cast<int>(std::sqrt(max_));
    std::vector<int> ret;
    std::vector<signed char> sieve(max_ + 1);
    int i = 2;
    for (; i <= sq_max; ++i) {
      if (!sieve[i]) {
        ret.emplace_back(i);
        for (int j = i * i; j <= max_; j += i)
          sieve[j] = true;
      }
    }

    for (; i <= max_; ++i) {
      if (!sieve[i])
        ret.emplace_back(i);
    }

    return ret;
  }

  int number_of_primes(int max_) {
    if (max_ < 2) return 0;
    const int sq_max = static_cast<int>(std::sqrt(max_));
    std::vector<signed char> sieve(max_ + 1);
    sieve[0] = sieve[1] = true;
    int i = 5, f = 4, cnt = 2;
    for (; i <= sq_max; i += (f = 6 - f)) {
      if (!sieve[i]) {
        ++cnt;
        for (int j = i * (i | 1); j <= max_; j += i * 2)
          sieve[j] = true;
      }
    }

    for (; i <= max_; i += (f = 6 - f))
      cnt += (!sieve[i]);

    return cnt;
  }
}  // namespace lib

#pragma endregion

int max_pow(int base, int max) {
  long long ret = 1;
  while (ret * base <= max) ret *= base;
  return static_cast<int>(ret);
}

void solve() {
  int N;
  std::cin >> N;

  auto primes = lib::primes_seq_under(N);
  primes.pop_back();
  mint ans = 1;

  // see(primes);

  for (auto&& p : primes) {
    ans *= max_pow(p, N);
    // see(p, max_pow(p, N));
  }

  std::cout << ans << "\n";
}

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  solve();
}