#pragma region template
// clang-format off

#ifdef LOCAL_NDEBUG
#include <headers.hpp>
#endif

// #define USE_EXTERNAL_CONTAINERS
// #define NO_PRINT_INF

#ifdef USE_EXTERNAL_CONTAINERS
#define PROPER
#include <boost/container/flat_map.hpp>
#include <boost/container/flat_set.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
template <class T>          using rb_tree    = __gnu_pbds::tree<T, __gnu_pbds::null_type, std::less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
template <class S, class T> using hash_table = __gnu_pbds::gp_hash_table<S, T>;
#endif

#ifdef LOCAL_DEBUG
#if (defined USE_EXTERNAL_CONTAINERS) || (defined NO_PRINT_INF) || (defined PROPER)
#include <../src/debugger.hpp>
#else
#include <debugger.hpp>
#endif
#endif

// #define PROPER

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

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

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

#ifdef LOCAL_DEBUG
#define STR(x) #x
#define STRINGIFY(x) STR(x)
#define FILE_LINE "[Debug] ./" __FILE__ ":" STRINGIFY(__LINE__)
#define see(...) debugger::multi_print(#__VA_ARGS__, __VA_ARGS__)
#define see2(arg) arg.debug_print(#arg)
#define here(...) debugger::os << FILE_LINE << " in " << __func__ << ": \e[32mReached\e[39m\n"
#define com(msg) debugger::os << FILE_LINE << " in " << __func__ << ":\n    \e[36mComment:\e[39m " << msg << "\n"
#define err(msg) debugger::os << FILE_LINE << " in " << __func__ << ":\n    \e[31mError:\e[39m " << msg << "\n"
#define local(...) do { __VA_ARGS__ } while (0)
#define alter(x, y) x
#else
#define see(...) (static_cast<void>(0))
#define see2(arg) (static_cast<void>(0))
#define here(...) (static_cast<void>(0))
#define com(msg) (static_cast<void>(0))
#define err(msg) (static_cast<void>(0))
#define local(...) (static_cast<void>(0))
#define alter(x, y) y
#endif

#if (defined LOCAL_DEBUG) && (!defined NOWARN)
#define warn(msg) debugger::os << FILE_LINE << " in " << __func__ << ":\n    \e[33mWarning:\e[39m " << msg << "\n"
#else
#define warn(msg) (static_cast<void>(0))
#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)) {auto p = static_cast<std::int64_t*>(std::malloc(1 << 30)); for (int i = 0; i < (1 << 27); p[i] = 1, i += (1 << 9)); std::cerr << (*p);}} while (0)
#define O_assert(expr) do {if(__builtin_expect(!(expr), 0)) {const auto X = std::string(1000, '-'); for(int i = 0; i < (1 << 18); i++) std::cout << X;}} while (0)
#endif

#define as(type, val) static_cast<std::decay_t<type>>(val)
#define INDIRECT(...) __VA_ARGS__

#define rep(loop_var, loop_end) \
  for ( \
    auto loop_var = as(std::make_signed_t<decltype(loop_end)>, 0); \
    loop_var < as(decltype(loop_var), loop_end); \
    ++loop_var \
  )
#define rng(loop_var, loop_start, loop_end, loop_increment) \
  for ( \
    auto loop_var = as(INDIRECT(std::make_signed_t<std::common_type_t<decltype(loop_start), decltype(loop_end)>>), loop_start); \
    ((loop_increment) > 0) ? (loop_var < as(decltype(loop_var), loop_end)) : (loop_var > as(decltype(loop_var), loop_end)); \
    loop_var += (loop_increment) \
  )
#define erng(loop_var, loop_start, loop_end, loop_increment) \
  for ( \
    auto loop_var = as(INDIRECT(std::make_signed_t<std::common_type_t<decltype(loop_start), decltype(loop_end)>>), loop_start); \
    ((loop_increment) > 0) ? (loop_var <= as(decltype(loop_var), loop_end)) : (loop_var >= as(decltype(loop_var), loop_end)); \
    loop_var += (loop_increment) \
  )

[[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... Ts> constexpr auto Min(const Ts... args) { return std::min({ as(std::common_type_t<Ts...>, args) ... }); }
template <class... Ts> constexpr auto Max(const Ts... args) { return std::max({ as(std::common_type_t<Ts...>, args) ... }); }

// clang-format on
#pragma endregion

#pragma region lib_static_modint

#define lib_mint 1
#define lib_static_modint 1

namespace lib {
  template <std::int32_t modulo> class static_modint {
    std::int32_t value;
    template <class Tp> static constexpr std::int32_t calc_inverse(Tp n) noexcept {
      Tp b = modulo, u = 1, v = 0, t;
      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);
      }
      if (u < 0) u += modulo;
      return static_cast<std::int32_t>(u);
    }

    template <class Tp> static constexpr std::int32_t clamp_ll(Tp v) noexcept {
      if (modulo <= v || v < -modulo) v %= modulo;
      if (v < 0) v += modulo;
      return static_cast<std::int32_t>(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:
    using type = std::int32_t;

    static constexpr type mod(void) noexcept {
      return modulo;
    }

    // constructor
    constexpr static_modint(void) noexcept : value(0) {}
    template <class ValueType> constexpr static_modint(const ValueType v) noexcept {
      if constexpr (std::is_integral_v<ValueType> && (std::numeric_limits<ValueType>::digits <= 32)) {
        value = v;
        clamp_self();
      } else {
        value = clamp_ll(v);
      }
    }
    constexpr static_modint(const std::int32_t 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<std::int64_t>(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<std::int64_t>(value) * calc_inverse(rhs.value));
    }

    constexpr static_modint<modulo> operator%(const static_modint<modulo> rhs) const NOEXCEPT {
      warn("operator% <static_modint, static_modint> : 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("operator& <static_modint, static_modint> : 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("operator| <static_modint, static_modint> : 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("operator^ <static_modint, static_modint> : 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("operator<< <static_modint, static_modint> : Are you sure you want to do this?");
      return static_modint<modulo>(static_cast<std::int64_t>(value) << rhs.value);
    }
    constexpr static_modint<modulo> operator>>(const static_modint<modulo> rhs) const noexcept {
      warn("operator>> <static_modint, static_modint> : 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<std::int64_t>(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<std::int64_t>(value) * calc_inverse(rhs.value));
      return *this;
    }

    constexpr static_modint<modulo>& operator%=(const static_modint<modulo> rhs) NOEXCEPT {
      warn("operator%= <static_modint, static_modint> : 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("operator&= <static_modint, static_modint> : 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("operator|= <static_modint, static_modint> : 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("operator^= <static_modint, static_modint> : 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("operator<<= <static_modint, static_modint> : Are you sure you want to do this?");
      value = clamp_ll(static_cast<std::int64_t>(value) << rhs.value);
      return *this;
    }
    constexpr static_modint<modulo>& operator>>=(const static_modint<modulo> rhs) noexcept {
      warn("operator>>= <static_modint, static_modint> : 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<std::int64_t>(value) + rhs);
    }
    template <class RhsType> constexpr static_modint<modulo> operator-(const RhsType rhs) const noexcept {
      return static_modint<modulo>(static_cast<std::int64_t>(value) - rhs);
    }
    template <class RhsType> constexpr static_modint<modulo> operator*(const RhsType rhs) const noexcept {
      return static_modint<modulo>(static_cast<std::int64_t>(value) * rhs);
    }
    template <class RhsType> constexpr static_modint<modulo> operator/(const RhsType rhs) const NOEXCEPT {
      // O_assert(rhs != 0);
      std::int64_t 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("operator% <static_modint, " << debugger::type_name<RhsType> << "> : 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("operator& <static_modint, " << debugger::type_name<RhsType> << "> : 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("operator| <static_modint, " << debugger::type_name<RhsType> << "> : 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("operator^ <static_modint, " << debugger::type_name<RhsType> << "> : 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("operator<< <static_modint, " << debugger::type_name<RhsType> << "> : Are you sure you want to do this?");
      return static_modint<modulo>(static_cast<std::int64_t>(value) << rhs);
    }
    template <class RhsType> constexpr static_modint<modulo> operator>>(const RhsType rhs) const noexcept {
      warn("operator>> <static_modint, " << debugger::type_name<RhsType> << "> : 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<std::int64_t>(value) + rhs);
      return *this;
    }
    template <class RhsType> constexpr static_modint<modulo>& operator-=(const RhsType rhs) noexcept {
      value = clamp_ll(static_cast<std::int64_t>(value) - rhs);
      return *this;
    }
    template <class RhsType> constexpr static_modint<modulo>& operator*=(const RhsType rhs) noexcept {
      value = clamp_ll(static_cast<std::int64_t>(value) * rhs);
      return *this;
    }
    template <class RhsType> constexpr static_modint<modulo>& operator/=(const RhsType rhs) NOEXCEPT {
      // O_assert(rhs != 0);
      std::int64_t 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("operator%= <static_modint, " << debugger::type_name<RhsType> << "> : 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("operator&= <static_modint, " << debugger::type_name<RhsType> << "> : 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("operator|= <static_modint, " << debugger::type_name<RhsType> << "> : 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("operator^= <static_modint, " << debugger::type_name<RhsType> << "> : 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("operator<<= <static_modint, " << debugger::type_name<RhsType> << "> : Are you sure you want to do this?");
      value = clamp_ll(static_cast<std::int64_t>(value) << rhs);
      return *this;
    }
    template <class RhsType> constexpr static_modint<modulo>& operator>>=(const RhsType rhs) noexcept {
      warn("operator>>= <static_modint, " << debugger::type_name<RhsType> << "> : Are you sure you want to do this?");
      value >>= rhs;
      return *this;
    }

    constexpr bool operator!(void) const noexcept {
      warn("operator! <static_modint> : Are you sure you want to do this?");
      return value == 0;
    }
    constexpr static_modint<modulo> operator~(void) const noexcept {
      warn("operator~ <static_modint> : 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 {
      std::int32_t ret = value;
      ++(*this);
      return static_modint<modulo>(ret, true);
    }
    constexpr static_modint<modulo> operator--(int) noexcept {
      std::int32_t 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("operator< <static_modint, static_modint> : Are you sure you want to do this?");
      return value < rhs.value;
    }
    constexpr bool operator<=(const static_modint<modulo> rhs) const noexcept {
      warn("operator<= <static_modint, static_modint> : Are you sure you want to do this?");
      return value <= rhs.value;
    }
    constexpr bool operator>(const static_modint<modulo> rhs) const noexcept {
      warn("operator> <static_modint, static_modint> : Are you sure you want to do this?");
      return value > rhs.value;
    }
    constexpr bool operator>=(const static_modint<modulo> rhs) const noexcept {
      warn("operator>= <static_modint, static_modint> : 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("operator< <static_modint, " << debugger::type_name<RhsType> << "> : Are you sure you want to do this?");
      return value < rhs;
    }
    template <class RhsType> constexpr bool operator<=(const RhsType rhs) const noexcept {
      warn("operator<= <static_modint, " << debugger::type_name<RhsType> << "> : Are you sure you want to do this?");
      return value <= rhs;
    }
    template <class RhsType> constexpr bool operator>(const RhsType rhs) const noexcept {
      warn("operator> <static_modint, " << debugger::type_name<RhsType> << "> : Are you sure you want to do this?");
      return value > rhs;
    }
    template <class RhsType> constexpr bool operator>=(const RhsType rhs) const noexcept {
      warn("operator>= <static_modint, " << debugger::type_name<RhsType> << "> : Are you sure you want to do this?");
      return value >= rhs;
    }

    constexpr operator std::int32_t() const noexcept {
      return value;
    }

    friend std::istream& operator>>(std::istream& is, static_modint<modulo>& rhs) {
      std::int64_t tmp;
      is >> tmp;
      if (tmp < -modulo || modulo <= tmp) tmp %= modulo;
      if (tmp < 0) tmp += modulo;
      rhs.value = static_cast<std::int32_t>(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 = std::int32_t>
    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<true>(-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<std::int32_t, std::int32_t> to_frac(void) const noexcept {
      std::int32_t x = modulo - value, y = value, u = 1, v = 1;
      std::pair<std::int32_t, std::int32_t> ret {value, 1};

      std::int32_t num = value, den = 1;
      std::int32_t cost = num + den;

      while (x > 0) {
        if (x <= num) {
          std::int32_t 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;
          }
        }
        std::int32_t q = y / x;
        y              = y % x;
        v += q * u;
        q = x / y;
        x = x % y;
        u += q * v;
      }

      return ret;
    }
  };

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

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

  template <class LhsType, std::int32_t 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<< <" << debugger::type_name<LhsType> << ", static_modint> : Are you sure you want to do this?");
    return static_modint<modulo>(static_cast<std::int64_t>(lhs) << static_cast<std::int32_t>(rhs));
  }
  template <class LhsType, std::int32_t 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>> <" << debugger::type_name<LhsType> << ", static_modint> : Are you sure you want to do this?");
    return static_modint<modulo>(lhs >> static_cast<std::int32_t>(rhs));
  }

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

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

  template <class LhsType, std::int32_t modulo>
  constexpr LhsType& operator&=(LhsType& lhs, const static_modint<modulo> rhs) noexcept {
    warn("operator&= <" << debugger::type_name<LhsType> << ", static_modint> : Are you sure you want to do this?");
    return lhs &= static_cast<std::int32_t>(rhs);
  }
  template <class LhsType, std::int32_t modulo>
  constexpr LhsType& operator|=(LhsType& lhs, const static_modint<modulo> rhs) noexcept {
    warn("operator|= <" << debugger::type_name<LhsType> << ", static_modint> : Are you sure you want to do this?");
    return lhs |= static_cast<std::int32_t>(rhs);
  }
  template <class LhsType, std::int32_t modulo>
  constexpr LhsType& operator^=(LhsType& lhs, const static_modint<modulo> rhs) noexcept {
    warn("operator^= <" << debugger::type_name<LhsType> << ", static_modint> : Are you sure you want to do this?");
    return lhs ^= static_cast<std::int32_t>(rhs);
  }
  template <class LhsType, std::int32_t modulo>
  constexpr LhsType& operator<<=(LhsType& lhs, const static_modint<modulo> rhs) noexcept {
    warn("operator<<= <" << debugger::type_name<LhsType> << ", static_modint> : Are you sure you want to do this?");
    return lhs <<= static_cast<std::int32_t>(rhs);
  }
  template <class LhsType, std::int32_t modulo>
  constexpr LhsType& operator>>=(LhsType& lhs, const static_modint<modulo> rhs) noexcept {
    warn("operator>>= <" << debugger::type_name<LhsType> << ", static_modint> : Are you sure you want to do this?");
    return lhs >>= static_cast<std::int32_t>(rhs);
  }

  template <class LhsType, std::int32_t modulo>
  constexpr bool operator<(const LhsType lhs, const static_modint<modulo> rhs) noexcept {
    warn("operator< <" << debugger::type_name<LhsType> << ", static_modint> : Are you sure you want to do this?");
    return lhs < static_cast<std::int32_t>(rhs);
  }
  template <class LhsType, std::int32_t modulo>
  constexpr bool operator<=(const LhsType lhs, const static_modint<modulo> rhs) noexcept {
    warn("operator<= <" << debugger::type_name<LhsType> << ", static_modint> : Are you sure you want to do this?");
    return lhs < static_cast<std::int32_t>(rhs);
  }
  template <class LhsType, std::int32_t modulo>
  constexpr bool operator>(const LhsType lhs, const static_modint<modulo> rhs) noexcept {
    warn("operator> <" << debugger::type_name<LhsType> << ", static_modint> : Are you sure you want to do this?");
    return lhs < static_cast<std::int32_t>(rhs);
  }
  template <class LhsType, std::int32_t modulo>
  constexpr bool operator>=(const LhsType lhs, const static_modint<modulo> rhs) noexcept {
    warn("operator>= <" << debugger::type_name<LhsType> << ", static_modint> : Are you sure you want to do this?");
    return lhs < static_cast<std::int32_t>(rhs);
  }
}  // namespace lib

#pragma endregion

using mint = lib::static_modint<1000000007>;

void solve() {
  mint n;
  std::cin >> n;
  std::cout << n << "\n";
}

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