#pragma region template
// clang-format off

#ifdef ONLINE_JUDGE
#pragma GCC optimize "fast-math"
#endif

#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 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)
#include <../src/debugger.hpp>
#else
#include <debugger.hpp>
#endif
#endif

// #define PROPER
#define _USE_MATH_DEFINES

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

#include <cassert>
#include <cctype>
#include <cmath>
#include <cstddef>
#include <cstdint>
#include <cstdlib>
#include <algorithm>
#include <array>
#include <bitset>
#include <charconv>
#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

using namespace std::literals;

#ifdef LOCAL_DEBUG
#define CP_LIBRARY_DEBUG_LEVEL 2
#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__ << ": \033[32mReached\033[39m\n"
#define com(msg) debugger::os << FILE_LINE << " in " << __func__ << ":\n    \033[36mComment:\033[39m " << msg << "\n"
#define err(msg) debugger::os << FILE_LINE << " in " << __func__ << ":\n    \033[31mError:\033[39m " << msg << "\n"
#define local(...) do { __VA_ARGS__ } while (0)
#define alter(x, y) x
#define pass (com("ToDo: Fill here"), true)
#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
#ifdef __INTELLISENSE__
#define pass (static_cast<void>(0))
#else
#define pass static_assert(false)
#endif
#endif

#if (defined LOCAL_DEBUG) && (!defined NOWARN)
#define warn(msg) debugger::os << FILE_LINE << " in " << __func__ << ":\n    \033[33mWarning:\033[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 CP_LIBRARY_WARN(msg) warn(msg)
#define CP_LIBRARY_ASSERT(...) O_assert(__VA_ARGS__)

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

// clang-format on
#pragma endregion

//! @file static_modint.hpp

#ifndef CP_LIBRARY_STATIC_MODINT_HPP
#  define CP_LIBRARY_STATIC_MODINT_HPP

#  include <cassert>
#  include <cstdint>
#  include <iostream>
#  include <limits>
#  include <type_traits>

#  define CP_LIBRARY_USE_CONSTEXPR

#  ifndef CP_LIBRARY_WARN
#    if (CP_LIBRARY_DEBUG_LEVEL >= 1)
//! @brief Print warning message
//! @note You can suppress the warning by uncommenting the following line
#      define CP_LIBRARY_WARN(msg) (std::cerr << (msg) << '\n')
// #  define CP_LIBRARY_WARN(msg) (static_cast<void>(0))
#    else
#      define CP_LIBRARY_WARN(msg) (static_cast<void>(0))
#      undef CP_LIBRARY_USE_CONSTEXPR
#      define CP_LIBRARY_USE_CONSTEXPR constexpr
#    endif
#    define CP_LIBRARY_WARN_NOT_DEFINED
#  endif

#  ifndef CP_LIBRARY_ASSERT
//! @brief Assert macro
#    define CP_LIBRARY_ASSERT(...) assert(__VA_ARGS__)
#    define CP_LIBRARY_ASSERT_NOT_DEFINED
#  endif

namespace lib {

//! @brief modint (for compile-time constant modulo)
//! @tparam modulo modulo (e.g. 1000000007).
template <std::int_least32_t modulo,
          std::enable_if_t<(1 < modulo) && (modulo < std::numeric_limits<std::int_least32_t>::max() / 2),
                           std::nullptr_t> = nullptr>
struct static_modint {
private:
  std::int_least32_t value;

  //! @param n non-zero integer
  //! @return multiplicative inverse of n
  template <typename Tp>
  [[nodiscard]] static std::int_least32_t calc_inverse(Tp n) {
    CP_LIBRARY_ASSERT(n != 0);

    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::int_least32_t>(u);
  }

  //! @brief Calculate modulo and keep the value within [0, modulo)
  //! @param v integer
  //! @return integer within [0, modulo)
  //! @note Time complexity: O(1)
  template <typename Tp>
  [[nodiscard]] static constexpr std::int_least32_t clamp_ll(Tp v) noexcept {
#  pragma GCC diagnostic push
#  pragma GCC diagnostic ignored "-Wsign-compare"
    if (modulo <= v || v < -modulo)
      v %= modulo;
#  pragma GCC diagnostic pop

    if (v < 0)
      v += modulo;
    return static_cast<std::int_least32_t>(v);
  }

  //! @brief Calculate modulo and keep the value within [0, modulo)
  //! @note Time complexity: O(1)
  constexpr void clamp_self() 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:
  //! @brief underlying integer type
  using type = std::int_least32_t;

  //! @return modulo (e.g. 1000000007)
  [[nodiscard]] static constexpr type mod() noexcept {
    return modulo;
  }

  //! @brief Create a modint of value 0
  constexpr static_modint() noexcept : value(0) {}

  //! @brief Create a modint without taking modulo
  constexpr static_modint(const type v, bool) noexcept : value(v) {}

  //! @brief Create a modint
  template <typename ValueType>
  constexpr static_modint(const ValueType v) noexcept : value() {
    if constexpr (std::is_integral_v<ValueType> && (std::numeric_limits<ValueType>::digits <= 32)) {
      value = v;
      clamp_self();
    } else {
      value = clamp_ll(v);
    }
  }

  [[nodiscard]] constexpr static_modint operator+(const static_modint rhs) const noexcept {
    return static_modint(value + rhs.value);
  }
  [[nodiscard]] constexpr static_modint operator-(const static_modint rhs) const noexcept {
    return static_modint(value - rhs.value);
  }
  [[nodiscard]] constexpr static_modint operator*(const static_modint rhs) const noexcept {
    return static_modint(static_cast<std::int_least64_t>(value) * rhs.value);
  }
  [[nodiscard]] static_modint operator/(const static_modint rhs) const {
    return static_modint(static_cast<std::int_least64_t>(value) * calc_inverse(rhs.value));
  }

  [[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint operator%(const static_modint rhs) const {
    CP_LIBRARY_WARN("static_modint::operator% : Are you sure you want to do this?");
    return static_modint(value % rhs.value);
  }

  [[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint operator&(const static_modint rhs) const {
    CP_LIBRARY_WARN("static_modint::operator& : Are you sure you want to do this?");
    return static_modint(value & rhs.value, true);
  }
  [[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint operator|(const static_modint rhs) const {
    CP_LIBRARY_WARN("static_modint::operator| : Are you sure you want to do this?");
    return static_modint(value | rhs.value);
  }
  [[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint operator^(const static_modint rhs) const {
    CP_LIBRARY_WARN("static_modint::operator^ : Are you sure you want to do this?");
    return static_modint(value ^ rhs.value);
  }
  [[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint operator<<(const static_modint rhs) const {
    CP_LIBRARY_WARN("static_modint::operator<< : Are you sure you want to do this?");
    return static_modint(static_cast<std::int_least64_t>(value) << rhs.value);
  }
  [[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint operator>>(const static_modint rhs) const {
    CP_LIBRARY_WARN("static_modint::operator>> : Are you sure you want to do this?");
    return static_modint(value >> rhs.value, true);
  }

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

  CP_LIBRARY_USE_CONSTEXPR static_modint& operator%=(const static_modint rhs) {
    CP_LIBRARY_WARN("static_modint::operator%= : Are you sure you want to do this?");
    value %= rhs.value;
    if (value < 0)
      value += modulo;
    return *this;
  }

  CP_LIBRARY_USE_CONSTEXPR static_modint& operator&=(const static_modint rhs) {
    CP_LIBRARY_WARN("static_modint::operator&= : Are you sure you want to do this?");
    value &= rhs.value;
    return *this;
  }
  CP_LIBRARY_USE_CONSTEXPR static_modint& operator|=(const static_modint rhs) {
    CP_LIBRARY_WARN("static_modint::operator|= : Are you sure you want to do this?");
    value |= rhs.value;
    clamp_self();
    return *this;
  }
  CP_LIBRARY_USE_CONSTEXPR static_modint& operator^=(const static_modint rhs) {
    CP_LIBRARY_WARN("static_modint::operator^= : Are you sure you want to do this?");
    value ^= rhs.value;
    clamp_self();
    return *this;
  }
  CP_LIBRARY_USE_CONSTEXPR static_modint& operator<<=(const static_modint rhs) {
    CP_LIBRARY_WARN("operator<<= : Are you sure you want to do this?");
    value = clamp_ll(static_cast<std::int_least64_t>(value) << rhs.value);
    return *this;
  }
  CP_LIBRARY_USE_CONSTEXPR static_modint& operator>>=(const static_modint rhs) {
    CP_LIBRARY_WARN("operator>>= : Are you sure you want to do this?");
    value >>= rhs.value;
    return *this;
  }

  template <typename RhsType>
  [[nodiscard]] constexpr static_modint operator+(const RhsType rhs) const noexcept {
    return static_modint(value + clamp_ll(rhs));
  }
  template <typename RhsType>
  [[nodiscard]] constexpr static_modint operator-(const RhsType rhs) const noexcept {
    return static_modint(value - clamp_ll(rhs));
  }
  template <typename RhsType>
  [[nodiscard]] constexpr static_modint operator*(const RhsType rhs) const noexcept {
    return static_modint(static_cast<std::int_least64_t>(value) * clamp_ll(rhs));
  }
  template <typename RhsType>
  [[nodiscard]] static_modint operator/(const RhsType rhs) const {
    std::int_least64_t mul = (rhs > 0) ? calc_inverse(rhs) : -calc_inverse(-rhs);
    return static_modint(value * mul);
  }

  template <typename RhsType>
  [[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint operator%(const RhsType rhs) const {
    CP_LIBRARY_WARN("static_modint::operator% : Are you sure you want to do this?");
    return static_modint(value % rhs, true);
  }

  template <typename RhsType>
  [[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint operator&(const RhsType rhs) const {
    CP_LIBRARY_WARN("static_modint::operator& : Are you sure you want to do this?");
    return static_modint(value & rhs, true);
  }
  template <typename RhsType>
  [[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint operator|(const RhsType rhs) const {
    CP_LIBRARY_WARN("static_modint::operator| : Are you sure you want to do this?");
    return static_modint(value | rhs);
  }
  template <typename RhsType>
  [[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint operator^(const RhsType rhs) const {
    CP_LIBRARY_WARN("static_modint::operator^ : Are you sure you want to do this?");
    return static_modint(value ^ rhs);
  }
  template <typename RhsType>
  [[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint operator<<(const RhsType rhs) const {
    CP_LIBRARY_WARN("static_modint::operator<< : Are you sure you want to do this?");
    return static_modint(static_cast<std::int_least64_t>(value) << rhs);
  }
  template <typename RhsType>
  [[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint operator>>(const RhsType rhs) const {
    CP_LIBRARY_WARN("static_modint::operator>> : Are you sure you want to do this?");
    return static_modint(value >> rhs, true);
  }

  template <typename RhsType>
  constexpr static_modint& operator+=(const RhsType rhs) noexcept {
    value = clamp_ll(static_cast<std::int_least64_t>(value) + rhs);
    return *this;
  }
  template <typename RhsType>
  constexpr static_modint& operator-=(const RhsType rhs) noexcept {
    value = clamp_ll(static_cast<std::int_least64_t>(value) - rhs);
    return *this;
  }
  template <typename RhsType>
  constexpr static_modint& operator*=(const RhsType rhs) noexcept {
    value = clamp_ll(static_cast<std::int_least64_t>(value) * clamp_ll(rhs));
    return *this;
  }
  template <typename RhsType>
  static_modint& operator/=(const RhsType rhs) {
    std::int_least64_t mul = (rhs > 0) ? calc_inverse(rhs) : -calc_inverse(-rhs);
    value                  = clamp_ll(value * mul);
    return *this;
  }

  template <typename RhsType>
  CP_LIBRARY_USE_CONSTEXPR static_modint& operator%=(const RhsType rhs) {
    CP_LIBRARY_WARN("static_modint::operator%= : Are you sure you want to do this?");
    value %= rhs;
    return *this;
  }

  template <typename RhsType>
  CP_LIBRARY_USE_CONSTEXPR static_modint& operator&=(const RhsType rhs) {
    CP_LIBRARY_WARN("static_modint::operator&= : Are you sure you want to do this?");
    value &= rhs;
    return *this;
  }
  template <typename RhsType>
  CP_LIBRARY_USE_CONSTEXPR static_modint& operator|=(const RhsType rhs) {
    CP_LIBRARY_WARN("static_modint::operator|= : Are you sure you want to do this?");
    value |= rhs;
    clamp_self();
    return *this;
  }
  template <typename RhsType>
  CP_LIBRARY_USE_CONSTEXPR static_modint& operator^=(const RhsType rhs) {
    CP_LIBRARY_WARN("static_modint::operator^= : Are you sure you want to do this?");
    value ^= rhs;
    clamp_self();
    return *this;
  }
  template <typename RhsType>
  CP_LIBRARY_USE_CONSTEXPR static_modint& operator<<=(const RhsType rhs) {
    CP_LIBRARY_WARN("operator<<= : Are you sure you want to do this?");
    value = clamp_ll(static_cast<std::int_least64_t>(value) << rhs);
    return *this;
  }
  template <typename RhsType>
  CP_LIBRARY_USE_CONSTEXPR static_modint& operator>>=(const RhsType rhs) {
    CP_LIBRARY_WARN("operator>>= : Are you sure you want to do this?");
    value >>= rhs;
    return *this;
  }

  [[nodiscard]] CP_LIBRARY_USE_CONSTEXPR bool operator!() const {
    CP_LIBRARY_WARN("static_modint::operator! : Are you sure you want to do this?");
    return value == 0;
  }
  [[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint operator~() const {
    CP_LIBRARY_WARN("static_modint::operator~ : Are you sure you want to do this?");
    return static_modint(~value);
  }
  [[nodiscard]] constexpr static_modint operator-() const noexcept {
    return static_modint(value == 0 ? 0 : modulo - value, true);
  }
  [[nodiscard]] constexpr static_modint& operator+() const noexcept {
    return *this;
  }

  constexpr static_modint& operator++() noexcept {
    value = ((value + 1 == modulo) ? 0 : value + 1);
    return *this;
  }
  constexpr static_modint& operator--() noexcept {
    value = ((value == 0) ? modulo - 1 : value - 1);
    return *this;
  }
  constexpr static_modint operator++(int) noexcept {
    std::int_least32_t res = value;
    ++(*this);
    return static_modint(res, true);
  }
  constexpr static_modint operator--(int) noexcept {
    std::int_least32_t res = value;
    --(*this);
    return static_modint(res, true);
  }

  [[nodiscard]] constexpr bool operator==(const static_modint rhs) const noexcept {
    return value == rhs.value;
  }
  [[nodiscard]] constexpr bool operator!=(const static_modint rhs) const noexcept {
    return value != rhs.value;
  }
  [[nodiscard]] CP_LIBRARY_USE_CONSTEXPR bool operator<(const static_modint rhs) const {
    CP_LIBRARY_WARN("static_modint::operator< : Are you sure you want to do this?");
    return value < rhs.value;
  }
  [[nodiscard]] CP_LIBRARY_USE_CONSTEXPR bool operator<=(const static_modint rhs) const {
    CP_LIBRARY_WARN("static_modint::operator<= : Are you sure you want to do this?");
    return value <= rhs.value;
  }
  [[nodiscard]] CP_LIBRARY_USE_CONSTEXPR bool operator>(const static_modint rhs) const {
    CP_LIBRARY_WARN("static_modint::operator> : Are you sure you want to do this?");
    return value > rhs.value;
  }
  [[nodiscard]] CP_LIBRARY_USE_CONSTEXPR bool operator>=(const static_modint rhs) const {
    CP_LIBRARY_WARN("static_modint::operator>= : Are you sure you want to do this?");
    return value >= rhs.value;
  }

  template <typename RhsType>
  [[nodiscard]] constexpr bool operator==(const RhsType rhs) const noexcept {
    return value == rhs;
  }
  template <typename RhsType>
  [[nodiscard]] constexpr bool operator!=(const RhsType rhs) const noexcept {
    return value != rhs;
  }
  template <typename RhsType>
  [[nodiscard]] CP_LIBRARY_USE_CONSTEXPR bool operator<(const RhsType rhs) const {
    CP_LIBRARY_WARN("static_modint::operator< : Are you sure you want to do this?");
    return value < rhs;
  }
  template <typename RhsType>
  [[nodiscard]] CP_LIBRARY_USE_CONSTEXPR bool operator<=(const RhsType rhs) const {
    CP_LIBRARY_WARN("static_modint::operator<= : Are you sure you want to do this?");
    return value <= rhs;
  }
  template <typename RhsType>
  [[nodiscard]] CP_LIBRARY_USE_CONSTEXPR bool operator>(const RhsType rhs) const {
    CP_LIBRARY_WARN("static_modint::operator> : Are you sure you want to do this?");
    return value > rhs;
  }
  template <typename RhsType>
  [[nodiscard]] CP_LIBRARY_USE_CONSTEXPR bool operator>=(const RhsType rhs) const {
    CP_LIBRARY_WARN("static_modint::operator>= : Are you sure you want to do this?");
    return value >= rhs;
  }

  [[nodiscard]] constexpr operator std::int_least32_t() const {
    CP_LIBRARY_WARN("A value of type static_modint has been cast to type std::int_lease32_t.");
    return value;
  }

  //! @brief Read value (64-bit signed integer) from std::istream& is, take modulo, and store it in rhs.
  //! @return std::istream& is
  friend std::istream& operator>>(std::istream& is, static_modint& rhs) {
    std::int_least64_t tmp;
    is >> tmp;
    if (tmp < -modulo || modulo <= tmp)
      tmp %= modulo;
    if (tmp < 0)
      tmp += modulo;
    rhs.value = static_cast<std::int_least32_t>(tmp);
    return is;
  }
  //! @brief Print value to std::ostream& os
  //! @return std::ostream& os
  friend std::ostream& operator<<(std::ostream& os, static_modint rhs) {
    return os << rhs.value;
  }

  //! @return multiplicative inverse
  [[nodiscard]] static_modint inv() const {
    return static_modint(calc_inverse(value), true);
  }
  //! @tparam index_positive_guaranteed set true if and only if you can promise that index is positive
  //! @tparam Tp integer type (deduced from parameter)
  //! @param index index. This must be an integer, but doesn't have to be primitive.
  //! @return index-th power of the value
  //! @note Time complexity: O(log(index))
  template <bool index_positive_guaranteed = true, typename Tp = std::int_least32_t>
  [[nodiscard]] static_modint pow(Tp index) const noexcept {
    if constexpr (!index_positive_guaranteed) {
      if (value == 0)
        return static_modint(0, true);
      if (index == 0)
        return static_modint(1, true);
      if (index < 0)
        return static_modint(value, true).inv().pow<true>(-index);
    }
    static_modint res(1, true), base(value, true);
    while (index > 0) {
      if ((index & 1) == 1)
        res *= base;
      base *= base;
      index >>= 1;
    }
    return res;
  }
  //! @return a pair (a, b) such that b > 0, value is equal to a * (mult inverse of b), and (a + b) is minimal
  [[nodiscard]] constexpr std::pair<std::int_least32_t, std::int_least32_t> to_frac() const noexcept {
    std::int_least32_t x = modulo - value, y = value, u = 1, v = 1;
    std::pair<std::int_least32_t, std::int_least32_t> res {value, 1};

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

    while (x > 0) {
      if (x <= num) {
        std::int_least32_t q = num / x;
        num                  = num % x;
        den += q * u;
        if (num == 0)
          break;
        if (num + den < cost) {
          cost       = num + den;
          res.first  = num;
          res.second = den;
        }
      }
      std::int_least32_t q = y / x;
      y                    = y % x;
      v += q * u;
      q = x / y;
      x = x % y;
      u += q * v;
    }

    return res;
  }
};

template <typename LhsType, std::int_least32_t modulo>
[[nodiscard]] constexpr static_modint<modulo> operator+(const LhsType lhs, const static_modint<modulo> rhs) noexcept {
  return rhs + lhs;
}
template <typename LhsType, std::int_least32_t modulo>
[[nodiscard]] constexpr static_modint<modulo> operator-(const LhsType lhs, const static_modint<modulo> rhs) noexcept {
  return -rhs + lhs;
}
template <typename LhsType, std::int_least32_t modulo>
[[nodiscard]] constexpr static_modint<modulo> operator*(const LhsType lhs, const static_modint<modulo> rhs) noexcept {
  return rhs * lhs;
}
template <typename LhsType, std::int_least32_t modulo>
[[nodiscard]] static_modint<modulo> operator/(const LhsType lhs, const static_modint<modulo> rhs) {
  return rhs.inv() * lhs;
}

template <typename LhsType, std::int_least32_t modulo>
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint<modulo>
operator%(const LhsType lhs, const static_modint<modulo> rhs) {
  CP_LIBRARY_WARN("static_modint::operator% : Are you sure you want to do this?");
  return static_modint<modulo>(lhs % static_cast<std::int_least32_t>(rhs), true);
}

template <typename LhsType, std::int_least32_t modulo, std::enable_if_t<std::is_integral_v<LhsType>, std::nullptr_t> = nullptr>
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint<modulo>
operator<<(const LhsType lhs, const static_modint<modulo> rhs) {
  CP_LIBRARY_WARN("static_modint::operator<< : Are you sure you want to do this?");
  return static_modint<modulo>(static_cast<std::int_least64_t>(lhs) << static_cast<std::int_least32_t>(rhs));
}
template <typename LhsType, std::int_least32_t modulo, std::enable_if_t<std::is_integral_v<LhsType>, std::nullptr_t> = nullptr>
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR static_modint<modulo>
operator>>(const LhsType lhs, const static_modint<modulo> rhs) {
  CP_LIBRARY_WARN("static_modint::operator>> : Are you sure you want to do this?");
  return static_modint<modulo>(lhs >> static_cast<std::int_least32_t>(rhs));
}

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

template <typename LhsType, std::int_least32_t modulo>
CP_LIBRARY_USE_CONSTEXPR LhsType& operator%=(LhsType& lhs, const static_modint<modulo> rhs) {
  CP_LIBRARY_WARN("static_modint::operator%= : Are you sure you want to do this?");
  return lhs %= static_cast<std::int_least32_t>(rhs);
}

template <typename LhsType, std::int_least32_t modulo>
CP_LIBRARY_USE_CONSTEXPR LhsType& operator&=(LhsType& lhs, const static_modint<modulo> rhs) {
  CP_LIBRARY_WARN("static_modint::operator&= : Are you sure you want to do this?");
  return lhs &= static_cast<std::int_least32_t>(rhs);
}
template <typename LhsType, std::int_least32_t modulo>
CP_LIBRARY_USE_CONSTEXPR LhsType& operator|=(LhsType& lhs, const static_modint<modulo> rhs) {
  CP_LIBRARY_WARN("static_modint::operator|= : Are you sure you want to do this?");
  return lhs |= static_cast<std::int_least32_t>(rhs);
}
template <typename LhsType, std::int_least32_t modulo>
CP_LIBRARY_USE_CONSTEXPR LhsType& operator^=(LhsType& lhs, const static_modint<modulo> rhs) {
  CP_LIBRARY_WARN("static_modint::operator^= : Are you sure you want to do this?");
  return lhs ^= static_cast<std::int_least32_t>(rhs);
}
template <typename LhsType, std::int_least32_t modulo>
CP_LIBRARY_USE_CONSTEXPR LhsType& operator<<=(LhsType& lhs, const static_modint<modulo> rhs) {
  CP_LIBRARY_WARN("operator<<= : Are you sure you want to do this?");
  return lhs <<= static_cast<std::int_least32_t>(rhs);
}
template <typename LhsType, std::int_least32_t modulo>
CP_LIBRARY_USE_CONSTEXPR LhsType& operator>>=(LhsType& lhs, const static_modint<modulo> rhs) {
  CP_LIBRARY_WARN("operator>>= : Are you sure you want to do this?");
  return lhs >>= static_cast<std::int_least32_t>(rhs);
}

template <typename LhsType, std::int_least32_t modulo>
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR bool operator<(const LhsType lhs, const static_modint<modulo> rhs) {
  CP_LIBRARY_WARN("static_modint::operator< : Are you sure you want to do this?");
  return lhs < static_cast<std::int_least32_t>(rhs);
}
template <typename LhsType, std::int_least32_t modulo>
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR bool operator<=(const LhsType lhs, const static_modint<modulo> rhs) {
  CP_LIBRARY_WARN("static_modint::operator<= : Are you sure you want to do this?");
  return lhs < static_cast<std::int_least32_t>(rhs);
}
template <typename LhsType, std::int_least32_t modulo>
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR bool operator>(const LhsType lhs, const static_modint<modulo> rhs) {
  CP_LIBRARY_WARN("static_modint::operator> : Are you sure you want to do this?");
  return lhs < static_cast<std::int_least32_t>(rhs);
}
template <typename LhsType, std::int_least32_t modulo>
[[nodiscard]] CP_LIBRARY_USE_CONSTEXPR bool operator>=(const LhsType lhs, const static_modint<modulo> rhs) {
  CP_LIBRARY_WARN("static_modint::operator>= : Are you sure you want to do this?");
  return lhs < static_cast<std::int_least32_t>(rhs);
}

}  // namespace lib

#  undef CP_LIBRARY_USE_CONSTEXPR

#  ifdef CP_LIBRARY_WARN_NOT_DEFINED
#    undef CP_LIBRARY_WARN
#    undef CP_LIBRARY_WARN_NOT_DEFINED
#    ifdef CP_LIBRARY_WARN
#      undef CP_LIBRARY_WARN
#    endif
#  endif

#  ifdef CP_LIBRARY_ASSERT_NOT_DEFINED
#    undef CP_LIBRARY_ASSERT
#    undef CP_LIBRARY_ASSERT_NOT_DEFINED
#  endif

#endif  // CP_LIBRARY_STATIC_MODINT_HPP

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

  using mint = lib::static_modint<998244353>;

  std::vector<mint> lock_unused(N + 1), lock_used__(N + 1), free_unused(N + 1), free_used__(N + 1);
  lock_unused[0] = 1;

  rep(i, N) {
    if (S[i] == 'a') {
      here();
      lock_used__[i + 1] += lock_unused[i];
      free_used__[i + 1] += free_unused[i];
    } else {
      here();
      // a
      free_used__[i + 1] += lock_unused[i];
      free_used__[i + 1] += free_unused[i];

      // S[i]
      lock_unused[i + 1] += lock_unused[i];
      lock_used__[i + 1] += lock_used__[i];
      free_unused[i + 1] += free_unused[i];
      free_used__[i + 1] += free_used__[i];
    }

    // for (char c = 'b'; c < S[i]; ++c) {
    //   free_unused[i + 1] += free_unused[i];
    //   free_unused[i + 1] += lock_unused[i];
    //   free_used__[i + 1] += free_used__[i];
    //   free_used__[i + 1] += lock_used__[i];
    // }

    int d = Max(0, S[i] - 'b');
    see(S[i], d);
    free_unused[i + 1] += free_unused[i] * d;
    free_unused[i + 1] += lock_unused[i] * d;
    free_used__[i + 1] += free_used__[i] * d;
    free_used__[i + 1] += lock_used__[i] * d;

    d = Max(0, 'z' - S[i]);
    see(S[i], d);
    free_unused[i + 1] += free_unused[i] * d;
    free_used__[i + 1] += free_used__[i] * d;
  }

  see(lock_unused, lock_used__, free_unused, free_used__);

  std::cout << free_used__.back() << "\n";
}

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout << std::fixed << std::setprecision(25);

  solve();
}