#line 1 "other-workspace\\749.cpp"
#include <bits/stdc++.h>

#line 2 "Library\\src\\algebra\\linear\\matrix.hpp"

/**
 * @file matrix.hpp
 * @brief Matrix
 * @date 2021-02-15
 *
 *
 */

#line 13 "Library\\src\\algebra\\linear\\matrix.hpp"

namespace workspace {

/**
 * @brief Fixed size matrix.
 *
 * @tparam _Scalar
 * @tparam _Rows Number of rows
 * @tparam _Cols Number of columns
 */
template <class _Scalar, std::size_t _Rows = 0, std::size_t _Cols = _Rows>
class matrix {
 public:
  _Scalar __data[_Rows][_Cols] = {};

  using value_type = _Scalar;
  using size_type = std::size_t;

  constexpr static matrix eye() {
    static_assert(_Rows == _Cols);

    matrix __e;
    for (size_type __d = 0; __d != _Rows; ++__d) __e.__data[__d][__d] = 1;
    return __e;
  }

  constexpr operator decltype((__data))() { return __data; }
  constexpr operator decltype(
      std::declval<const matrix>().__data) const&() const {
    return __data;
  }

  constexpr auto begin() { return __data; }
  constexpr auto begin() const { return __data; }

  constexpr auto end() { return __data + _Rows; }
  constexpr auto end() const { return __data + _Rows; }

  constexpr size_type rows() const { return _Rows; }

  constexpr size_type cols() const { return _Cols; }

  constexpr auto transpose() const {
    matrix<_Scalar, _Cols, _Rows> __t;

    for (size_type __r = 0; __r != _Rows; ++__r)
      for (size_type __c = 0; __c != _Cols; ++__c)
        __t.__data[__c][__r] = __data[__r][__c];

    return __t;
  }

  constexpr matrix operator+() const { return *this; }

  constexpr matrix operator-() const {
    matrix __cp = *this;

    for (auto& __v : __cp.__data)
      for (auto& __e : __v) __e = -__e;

    return __cp;
  }

  template <class _Matrix> constexpr matrix& operator+=(const _Matrix& __x) {
    auto __m = std::min(_Rows, __x.rows());
    auto __n = std::min(_Cols, __x.cols());

    for (size_type __r = 0; __r != __m; ++__r)
      for (size_type __c = 0; __c != __n; ++__c)
        __data[__r][__c] += __x[__r][__c];

    return *this;
  }

  template <class _Matrix>
  constexpr matrix operator+(const _Matrix& __x) const {
    return matrix(*this) += __x;
  }

  template <class _Matrix> constexpr matrix& operator-=(const _Matrix& __x) {
    auto __m = std::min(_Rows, __x.rows());
    auto __n = std::min(_Cols, __x.cols());

    for (size_type __r = 0; __r != __m; ++__r)
      for (size_type __c = 0; __c != __n; ++__c)
        __data[__r][__c] -= __x[__r][__c];

    return *this;
  }

  template <class _Matrix>
  constexpr matrix operator-(const _Matrix& __x) const {
    return matrix(*this) -= __x;
  }

  template <class _Scalar2>
  constexpr matrix& operator*=(const matrix<_Scalar2, _Cols, _Cols>& __x) {
    if (this == &__x) return operator=(operator*(__x));

    for (auto& __r : __data) {
      _Scalar __tmp[_Cols] = {};

      auto __v = *__x.__data;
      for (auto& __w : __tmp) {
        auto __i = __v++;
        for (const auto& __e : __r) __w += __e * *__i, __i += _Cols;
      }

      auto __w = __tmp;
      for (auto& __e : __r) __e = std::move(*__w++);
    }

    return *this;
  }

  template <class _Scalar2, size_type _Rows2, size_type _Cols2>
  constexpr auto operator*(const matrix<_Scalar2, _Rows2, _Cols2>& __x) const {
    matrix<typename std::common_type<_Scalar, _Scalar2>::type, _Rows, _Cols2>
        __m;

    auto __w = *__m.__data;
    for (const auto& __r : __data)
      for (auto __v = *__x.__data, __v_end = __v + _Cols2; __v != __v_end;
           ++__w) {
        auto __i = __v++;
        for (auto __e = __r; __e != __r + std::min(_Cols, _Rows2); ++__e)
          *__w += *__e * *__i, __i += _Cols2;
      }

    return __m;
  }

  // template <class _Matrix>
  // constexpr
  //     typename std::enable_if<!std::is_convertible<_Matrix,
  //     value_type>::value,
  //                             matrix<_Scalar>>::type
  //     operator*(const _Matrix& __x) const {
  //   matrix<_Scalar> __m(_Rows, __x.cols());

  //   for (size_type __r = 0; __r != _Rows; ++__r)
  //     for (size_type __i = 0; __i != __x.cols(); ++__i)
  //       for (size_type __c = 0; __c != std::min(_Cols, __x.rows()); ++__c)
  //         __m[__r][__i] += __data[__r][__c] * __x[__c][__i];

  //   return __m;
  // }

  constexpr matrix& operator*=(const value_type& __x) {
    for (auto& __v : __data)
      for (auto& __e : __v) __e *= __x;

    return *this;
  }

  constexpr matrix operator*(const value_type& __x) const {
    return matrix(*this) *= __x;
  }

  constexpr matrix& operator/=(const value_type& __x) {
    assert(__x != value_type(0));

    for (auto& __v : __data)
      for (auto& __e : __v) __e /= __x;

    return *this;
  }

  constexpr matrix operator/(const value_type& __x) const {
    return matrix(*this) /= __x;
  }

  template <class _Int> constexpr matrix pow(_Int __e) const {
    assert(0 <= __e);

    matrix __m = eye();
    for (matrix __cp = *this; __e; __cp *= __cp, __e >>= 1)
      if (__e & 1) __m *= __cp;

    return __m;
  }

  template <class _Os>
  constexpr friend _Os& operator<<(_Os& __os, const matrix& __x) {
    for (auto __i = __x.begin(); __i != __x.end(); ++__i, __os << '\n')
      for (size_type __c = 0; __c != _Cols; ++__c)
        __c ? void(__os << ' ') : (void)0, __os << *(*__i + __c);

    return __os;
  }
};  // namespace workspace

/**
 * @brief Dynamic matrix.
 *
 * @tparam _Scalar
 * @tparam _Rows Number of rows
 * @tparam _Cols Number of columns
 */
template <class _Scalar>
class matrix<_Scalar, 0, 0> : public std::valarray<std::valarray<_Scalar>> {
  using base = std::valarray<std::valarray<_Scalar>>;
  using row_type = typename base::value_type;

 public:
  using value_type = _Scalar;
  using size_type = std::size_t;

  using base::operator[];

  static matrix eye(size_type __n) {
    matrix __e(__n, __n);
    for (size_type __d = 0; __d != __n; ++__d) __e[__d][__d] = 1;
    return __e;
  }

  matrix() = default;

  matrix(size_type __n) : matrix(__n, __n) {}

  matrix(size_type __m, size_type __n) : base(row_type(__n), __m) {}

  template <class _Tp, typename = typename std::enable_if<
                           std::is_constructible<base, _Tp>::value &&
                           !std::is_constructible<size_type, _Tp>::value>::type>
  matrix(_Tp&& __x) : base(__x) {}

  matrix(std::initializer_list<row_type> __x) : base(__x) {}

  size_type rows() const { return base::size(); }

  size_type cols() const { return rows() ? operator[](0).size() : 0; }

  matrix transpose() const {
    matrix __t(cols(), rows());

    for (size_type __r = 0; __r != rows(); ++__r)
      for (size_type __c = 0; __c != cols(); ++__c)
        __t[__c][__r] = operator[](__r)[__c];

    return __t;
  }

  void resize(size_type __m, size_type __n) {
    matrix __t(__m, __n);

    if (rows() < __m) __m = rows();
    if (cols() < __n) __n = cols();

    for (size_type __r = 0; __r != __m; ++__r)
      for (size_type __c = 0; __c != __n; ++__c)
        __t[__r][__c] = std::move(operator[](__r)[__c]);

    base::swap(__t);
  }

  // binary operators {{

  template <class _Matrix, typename = void>
  struct is_valarray_based : std::false_type {};

  template <class _Matrix>
  struct is_valarray_based<
      _Matrix,
      typename std::enable_if<std::is_same<
          row_type, typename std::decay<decltype(std::declval<_Matrix>()[0])>::
                        type>::value>::type> : std::true_type {};

  template <class _Matrix>
  typename std::enable_if<!std::is_convertible<_Matrix, value_type>::value,
                          matrix&>::type
  operator*=(_Matrix&& __x) {
    return *this = operator*(std::forward<_Matrix>(__x));
  }

  template <class _Matrix>
  typename std::enable_if<!std::is_convertible<_Matrix, value_type>::value,
                          matrix>::type
  operator*(const _Matrix& __x) const {
    matrix __m(rows(), __x.cols());

    if constexpr (is_valarray_based<_Matrix>::value)
      for (size_type __r = 0; __r != rows(); ++__r)
        for (size_type __c = 0; __c != std::min(cols(), __x.rows()); ++__c)
          __m[__r] += operator[](__r)[__c] * __x[__c];

    else
      for (size_type __r = 0; __r != rows(); ++__r)
        for (size_type __i = 0; __i != __x.cols(); ++__i)
          for (size_type __c = 0; __c != std::min(cols(), __x.rows()); ++__c)
            __m[__r][__i] += operator[](__r)[__c] * __x[__c][__i];

    return __m;
  }

  matrix& operator*=(const value_type& __x) {
    for (size_type __r = 0; __r != rows(); ++__r)
      operator[](__r).operator*=(__x);

    return *this;
  }

  matrix operator*(const value_type& __x) const { return matrix(*this) *= __x; }

  friend matrix operator*(const value_type& __x, matrix __i) {
    for (size_type __r = 0; __r != __i.rows(); ++__r)
      __i.operator[](__r) = __x * __i.operator[](__r);

    return __i;
  }

  matrix& operator/=(const value_type& __x) {
    assert(__x != value_type(0));

    for (size_type __r = 0; __r != rows(); ++__r)
      operator[](__r).operator/=(__x);

    return *this;
  }

  matrix operator/(const value_type& __x) const { return matrix(*this) /= __x; }

  // }} binary operators

  template <class _Int> matrix pow(_Int __e) const {
    assert(0 <= __e);

    matrix __m = eye(rows());
    for (matrix __cp = *this; __e; __cp *= __cp, __e >>= 1)
      if (__e & 1) __m *= __cp;

    return __m;
  }

  // template <class _Is> friend _Is& operator>>(_Is& __is, matrix& __x) {
  //   for (size_type __r = 0; __r != __x.rows(); ++__r)
  //     for (size_type __c = 0; __c != __x.cols(); ++__c)
  //       __is >> __x.operator[](__r).operator[](__c);

  //   return __is;
  // }

  template <class _Os> friend _Os& operator<<(_Os& __os, const matrix& __x) {
    for (size_type __r = 0; __r != __x.rows(); ++__r, __os << '\n')
      for (size_type __c = 0; __c != __x.cols(); ++__c)
        __c ? void(__os << ' ') : (void)0,
            __os << __x.operator[](__r).operator[](__c);

    return __os;
  }
};

template <class _Scalar, std::size_t _Rows, std::size_t _Cols = _Rows>
class matrix_operator : public matrix<_Scalar, _Rows, _Cols> {
  using _Base = matrix<_Scalar, _Rows, _Cols>;

 public:
  constexpr operator _Base&() { return *this; }

  constexpr operator _Base const &() const { return *this; }

  constexpr matrix_operator() : _Base(_Base::eye()) {}

  constexpr matrix_operator(const _Base& __x) : _Base(__x) {}
};

}  // namespace workspace
#line 2 "Library\\src\\algebra\\modint.hpp"

/**
 * @file modint.hpp
 * @brief Modular Arithmetic
 */

#line 11 "Library\\src\\algebra\\modint.hpp"

#line 2 "Library\\src\\number_theory\\sqrt_mod.hpp"

/**
 * @file sqrt_mod.hpp
 * @brief Tonelli-Shanks Algorithm
 */

#line 2 "Library\\src\\number_theory\\pow_mod.hpp"

/**
 * @file mod_pow.hpp
 * @brief Modular Exponentiation
 */

#line 9 "Library\\src\\number_theory\\pow_mod.hpp"

#line 2 "Library\\src\\utils\\sfinae.hpp"

/**
 * @file sfinae.hpp
 * @brief SFINAE
 */

#line 10 "Library\\src\\utils\\sfinae.hpp"
#include <type_traits>

#ifndef __INT128_DEFINED__

#ifdef __SIZEOF_INT128__
#define __INT128_DEFINED__ 1
#else
#define __INT128_DEFINED__ 0
#endif

#endif

namespace std {

#if __INT128_DEFINED__

template <> struct make_signed<__uint128_t> { using type = __int128_t; };
template <> struct make_signed<__int128_t> { using type = __int128_t; };

template <> struct make_unsigned<__uint128_t> { using type = __uint128_t; };
template <> struct make_unsigned<__int128_t> { using type = __uint128_t; };

template <> struct is_signed<__uint128_t> : std::false_type {};
template <> struct is_signed<__int128_t> : std::true_type {};

template <> struct is_unsigned<__uint128_t> : std::true_type {};
template <> struct is_unsigned<__int128_t> : std::false_type {};

#endif

}  // namespace std

namespace workspace {

template <class Tp, class... Args> struct variadic_front { using type = Tp; };

template <class... Args> struct variadic_back;

template <class Tp> struct variadic_back<Tp> { using type = Tp; };

template <class Tp, class... Args> struct variadic_back<Tp, Args...> {
  using type = typename variadic_back<Args...>::type;
};

template <class type, template <class> class trait>
using enable_if_trait_type = typename std::enable_if<trait<type>::value>::type;

/**
 * @brief Return type of subscripting ( @c [] ) access.
 */
template <class _Tp>
using subscripted_type =
    typename std::decay<decltype(std::declval<_Tp&>()[0])>::type;

template <class Container>
using element_type = typename std::decay<decltype(*std::begin(
    std::declval<Container&>()))>::type;

template <class _Tp, class = void> struct has_begin : std::false_type {};

template <class _Tp>
struct has_begin<
    _Tp, std::__void_t<decltype(std::begin(std::declval<const _Tp&>()))>>
    : std::true_type {
  using type = decltype(std::begin(std::declval<const _Tp&>()));
};

template <class _Tp, class = void> struct has_size : std::false_type {};

template <class _Tp>
struct has_size<_Tp, std::__void_t<decltype(std::size(std::declval<_Tp>()))>>
    : std::true_type {};

template <class _Tp, class = void> struct has_resize : std::false_type {};

template <class _Tp>
struct has_resize<_Tp, std::__void_t<decltype(std::declval<_Tp>().resize(
                           std::declval<size_t>()))>> : std::true_type {};

template <class _Tp, class = void> struct has_mod : std::false_type {};

template <class _Tp>
struct has_mod<_Tp, std::__void_t<decltype(_Tp::mod)>> : std::true_type {};

template <class _Tp, class = void> struct is_integral_ext : std::false_type {};
template <class _Tp>
struct is_integral_ext<
    _Tp, typename std::enable_if<std::is_integral<_Tp>::value>::type>
    : std::true_type {};

#if __INT128_DEFINED__

template <> struct is_integral_ext<__int128_t> : std::true_type {};
template <> struct is_integral_ext<__uint128_t> : std::true_type {};

#endif

#if __cplusplus >= 201402

template <class _Tp>
constexpr static bool is_integral_ext_v = is_integral_ext<_Tp>::value;

#endif

template <typename _Tp, typename = void> struct multiplicable_uint {
  using type = uint_least32_t;
};
template <typename _Tp>
struct multiplicable_uint<
    _Tp,
    typename std::enable_if<(2 < sizeof(_Tp)) &&
                            (!__INT128_DEFINED__ || sizeof(_Tp) <= 4)>::type> {
  using type = uint_least64_t;
};

#if __INT128_DEFINED__

template <typename _Tp>
struct multiplicable_uint<_Tp,
                          typename std::enable_if<(4 < sizeof(_Tp))>::type> {
  using type = __uint128_t;
};

#endif

template <typename _Tp> struct multiplicable_int {
  using type =
      typename std::make_signed<typename multiplicable_uint<_Tp>::type>::type;
};

template <typename _Tp> struct multiplicable {
  using type = std::conditional_t<
      is_integral_ext<_Tp>::value,
      std::conditional_t<std::is_signed<_Tp>::value,
                         typename multiplicable_int<_Tp>::type,
                         typename multiplicable_uint<_Tp>::type>,
      _Tp>;
};

template <class> struct first_arg { using type = void; };

template <class _R, class _Tp, class... _Args>
struct first_arg<_R(_Tp, _Args...)> {
  using type = _Tp;
};

template <class _R, class _Tp, class... _Args>
struct first_arg<_R (*)(_Tp, _Args...)> {
  using type = _Tp;
};

template <class _G, class _R, class _Tp, class... _Args>
struct first_arg<_R (_G::*)(_Tp, _Args...)> {
  using type = _Tp;
};

template <class _G, class _R, class _Tp, class... _Args>
struct first_arg<_R (_G::*)(_Tp, _Args...) const> {
  using type = _Tp;
};

template <class _Tp, class = void> struct parse_compare : first_arg<_Tp> {};

template <class _Tp>
struct parse_compare<_Tp, std::__void_t<decltype(&_Tp::operator())>>
    : first_arg<decltype(&_Tp::operator())> {};

template <class _Container, class = void> struct get_dimension {
  static constexpr size_t value = 0;
};

template <class _Container>
struct get_dimension<_Container,
                     std::enable_if_t<has_begin<_Container>::value>> {
  static constexpr size_t value =
      1 + get_dimension<typename std::iterator_traits<
              typename has_begin<_Container>::type>::value_type>::value;
};

}  // namespace workspace
#line 11 "Library\\src\\number_theory\\pow_mod.hpp"

namespace workspace {

/**
 * @brief Compile time modular exponentiation.
 *
 * @param __x
 * @param __n Exponent
 * @param __mod Modulus
 * @return
 */
template <class _Tp>
constexpr std::enable_if_t<(is_integral_ext<_Tp>::value), _Tp> pow_mod(
    _Tp __x, _Tp __n, _Tp __mod) noexcept {
  assert(__mod > 0);

  using mul_type = typename multiplicable_uint<_Tp>::type;

  if ((__x %= __mod) < 0) __x += __mod;

  mul_type __y{1};

  while (__n) {
    if (__n & 1) (__y *= __x) %= __mod;
    __x = (mul_type)__x * __x % __mod;
    __n >>= 1;
  }

  return __y;
};

}  // namespace workspace
#line 10 "Library\\src\\number_theory\\sqrt_mod.hpp"

namespace workspace {

/**
 * @brief Compile time modular square root.
 *
 * @param __x
 * @param __mod Modulus
 * @return One if it exists. Otherwise -1.
 */
template <class _Tp>
constexpr std::enable_if_t<(is_integral_ext<_Tp>::value), _Tp> sqrt_mod(
    _Tp __x, _Tp __mod) noexcept {
  assert(__mod > 0);

  using mul_type = typename multiplicable_uint<_Tp>::type;

  if ((__x %= __mod) < 0) __x += __mod;

  if (!__x) return 0;

  if (__mod == 2) return __x;

  if (pow_mod(__x, __mod >> 1, __mod) != 1) return -1;

  _Tp __z = __builtin_ctz(__mod - 1), __q = __mod >> __z;

  mul_type __a = pow_mod(__x, (__q + 1) >> 1, __mod), __b = 2;
  while (pow_mod<_Tp>(__b, __mod >> 1, __mod) == 1) ++__b;
  __b = pow_mod<_Tp>(__b, __q, __mod);

  _Tp __shift = 0;

  for (auto __r = __a * __a % __mod * pow_mod(__x, __mod - 2, __mod) % __mod;
       __r != 1; (__r *= (__b *= __b) %= __mod) %= __mod) {
    auto __bsf = __z;

    for (auto __e = __r; __e != 1; --__bsf) (__e *= __e) %= __mod;

    while (++__shift != __bsf) (__b *= __b) %= __mod;

    (__a *= __b) %= __mod;
  }

  return __a;
};

}  // namespace workspace
#line 14 "Library\\src\\algebra\\modint.hpp"

namespace workspace {

namespace _modint_impl {

template <auto _Mod, unsigned _Storage> struct modint {
  static_assert(is_integral_ext<decltype(_Mod)>::value,
                "_Mod must be integral type.");

  using mod_type = std::make_signed_t<typename std::conditional<
      0 < _Mod, std::add_const_t<decltype(_Mod)>, decltype(_Mod)>::type>;

  using value_type = std::decay_t<mod_type>;

  using reference = value_type &;
  using const_reference = value_type const &;

  using mul_type = typename multiplicable_uint<value_type>::type;

  static mod_type mod;  // Modulus.

  static unsigned storage;

 private:
  template <class _Tp>
  using modint_if = std::enable_if_t<is_integral_ext<_Tp>::value, modint>;

  value_type value = 0;  // within [0, mod).

  struct direct_ctor_t {};
  constexpr static direct_ctor_t direct_ctor_tag{};

  // Direct constructor
  template <class _Tp>
  constexpr modint(_Tp __n, direct_ctor_t) noexcept : value(__n) {}

 public:
  constexpr modint() noexcept = default;

  template <class _Tp, class = std::enable_if_t<
                           std::is_convertible<_Tp, value_type>::value>>
  constexpr modint(_Tp __n) noexcept
      : value((__n %= mod) < _Tp(0) ? static_cast<value_type>(__n) + mod
                                    : static_cast<value_type>(__n)) {}

  constexpr modint(bool __n) noexcept : value(__n) {}

  constexpr operator reference() noexcept { return value; }

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

  // unary operators {{
  constexpr modint operator++(int) noexcept {
    modint __t{*this};
    operator++();
    return __t;
  }

  constexpr modint operator--(int) noexcept {
    modint __t{*this};
    operator--();
    return __t;
  }

  constexpr modint &operator++() noexcept {
    if (++value == mod) value = 0;
    return *this;
  }

  constexpr modint &operator--() noexcept {
    if (!value)
      value = mod - 1;
    else
      --value;
    return *this;
  }

  constexpr modint operator+() const noexcept { return *this; }

  constexpr modint operator-() const noexcept {
    return {value ? mod - value : 0, direct_ctor_tag};
  }

  // }} unary operators

  // operator+= {{

  constexpr modint &operator+=(const modint &__x) noexcept {
    if ((value += __x.value) >= mod) value -= mod;
    return *this;
  }

  template <class _Tp> constexpr modint_if<_Tp> &operator+=(_Tp __x) noexcept {
    __x %= mod, value += __x;
    if (value < 0)
      value += mod;
    else if (value >= mod)
      value -= mod;
    return *this;
  }

  // }} operator+=

  // operator+ {{

  template <class _Tp>
  constexpr modint_if<_Tp> operator+(_Tp const &__x) const noexcept {
    return modint{*this} += __x;
  }

  constexpr modint operator+(modint __x) const noexcept { return __x += *this; }

  template <class _Tp>
  constexpr friend modint_if<_Tp> operator+(_Tp const &__x,
                                            modint __y) noexcept {
    return __y += __x;
  }

  // }} operator+

  // operator-= {{

  constexpr modint &operator-=(const modint &__x) noexcept {
    if ((value -= __x.value) < 0) value += mod;
    return *this;
  }

  template <class _Tp> constexpr modint_if<_Tp> &operator-=(_Tp __x) noexcept {
    __x %= mod, value -= __x;
    if (value < 0)
      value += mod;
    else if (value >= mod)
      value -= mod;
    return *this;
  }

  // }} operator-=

  // operator- {{

  template <class _Tp>
  constexpr modint_if<_Tp> operator-(_Tp const &__x) const noexcept {
    return modint{*this} -= __x;
  }

  constexpr modint operator-(const modint &__x) const noexcept {
    return modint{*this} -= __x;
  }

  template <class _Tp>
  constexpr friend modint_if<_Tp> operator-(_Tp __x,
                                            const modint &__y) noexcept {
    if (((__x -= __y.value) %= mod) < 0) __x += mod;
    return {__x, direct_ctor_tag};
  }

  // }} operator-

  // operator*= {{

  constexpr modint &operator*=(const modint &__x) noexcept {
    value =
        static_cast<value_type>(value * static_cast<mul_type>(__x.value) % mod);
    return *this;
  }

  template <class _Tp> constexpr modint_if<_Tp> &operator*=(_Tp __x) noexcept {
    value = static_cast<value_type>(
        value * ((__x %= mod) < 0 ? mul_type(__x + mod) : mul_type(__x)) % mod);
    return *this;
  }

  // }} operator*=

  // operator* {{

  constexpr modint operator*(const modint &__x) const noexcept {
    return {static_cast<mul_type>(value) * __x.value % mod, direct_ctor_tag};
  }

  template <class _Tp>
  constexpr modint_if<_Tp> operator*(_Tp __x) const noexcept {
    __x %= mod;
    if (__x < 0) __x += mod;
    return {static_cast<mul_type>(value) * __x % mod, direct_ctor_tag};
  }

  template <class _Tp>
  constexpr friend modint_if<_Tp> operator*(_Tp __x,
                                            const modint &__y) noexcept {
    __x %= mod;
    if (__x < 0) __x += mod;
    return {static_cast<mul_type>(__x) * __y.value % mod, direct_ctor_tag};
  }

  // }} operator*

 protected:
  static value_type _mem(value_type __x) {
    static std::vector<value_type> __m{0, 1};
    static value_type __i = (__m.reserve(storage), 1);
    while (__i < __x) {
      ++__i;
      __m.emplace_back(mod - mul_type(mod / __i) * __m[mod % __i] % mod);
    }
    return __m[__x];
  }

  static value_type _div(mul_type __r, value_type __x) noexcept {
    assert(__x != value_type(0));
    if (!__r) return 0;

    std::make_signed_t<value_type> __v{};
    bool __neg = __x < 0 ? __x = -__x, true : false;

    if (static_cast<decltype(storage)>(__x) < storage)
      __v = _mem(__x);
    else {
      value_type __y{mod}, __u{1}, __t;

      while (__x)
        __t = __y / __x, __y ^= __x ^= (__y -= __t * __x) ^= __x,
        __v ^= __u ^= (__v -= __t * __u) ^= __u;

      if (__y < 0) __neg ^= 1;
    }

    if (__neg)
      __v = 0 < __v ? mod - __v : -__v;
    else if (__v < 0)
      __v += mod;

    return __r == mul_type(1) ? static_cast<value_type>(__v)
                              : static_cast<value_type>(__r * __v % mod);
  }

 public:
  static void reserve(unsigned __n) noexcept {
    if (storage < __n) storage = __n;
  }

  // operator/= {{

  constexpr modint &operator/=(const modint &__x) noexcept {
    if (value) value = _div(value, __x.value);
    return *this;
  }

  template <class _Tp> constexpr modint_if<_Tp> &operator/=(_Tp __x) noexcept {
    if (value) value = _div(value, __x %= mod);
    return *this;
  }

  // }} operator/=

  // operator/ {{

  constexpr modint operator/(const modint &__x) const noexcept {
    if (!value) return {};
    return {_div(value, __x.value), direct_ctor_tag};
  }

  template <class _Tp>
  constexpr modint_if<_Tp> operator/(_Tp __x) const noexcept {
    if (!value) return {};
    return {_div(value, __x %= mod), direct_ctor_tag};
  }

  template <class _Tp>
  constexpr friend modint_if<_Tp> operator/(_Tp __x,
                                            const modint &__y) noexcept {
    if (!__x) return {};
    if ((__x %= mod) < 0) __x += mod;
    return {_div(__x, __y.value), direct_ctor_tag};
  }

  // }} operator/

  constexpr modint inv() const noexcept { return _div(1, value); }

  template <class _Tp> constexpr modint pow(_Tp __e) const noexcept {
    static_assert(not std::is_floating_point<_Tp>::value);

    modint __r{mod != 1, direct_ctor_tag};

    for (modint __b{__e < _Tp(0) ? __e = -__e, _div(1, value) : value,
                                   direct_ctor_tag};
         __e; __e /= 2, __b *= __b)
      if (__e % 2) __r *= __b;

    return __r;
  }

  template <class _Tp>
  constexpr friend modint pow(modint __b, _Tp __e) noexcept {
    static_assert(not std::is_floating_point<_Tp>::value);

    if (__e < _Tp(0)) {
      __e = -__e;
      __b.value = _div(1, __b.value);
    }

    modint __r{mod != 1, direct_ctor_tag};

    for (; __e; __e /= 2, __b *= __b)
      if (__e % 2) __r *= __b;

    return __r;
  }

  constexpr modint sqrt() const noexcept {
    return {sqrt_mod(value, mod), direct_ctor_tag};
  }

  friend constexpr modint sqrt(const modint &__x) noexcept {
    return {sqrt_mod(__x.value, mod), direct_ctor_tag};
  }

  friend std::istream &operator>>(std::istream &__is, modint &__x) noexcept {
    std::string __s;
    __is >> __s;
    bool __neg = false;
    if (__s.front() == '-') {
      __neg = true;
      __s.erase(__s.begin());
    }
    __x = 0;
    for (char __c : __s) __x = __x * 10 + (__c - '0');
    if (__neg) __x = -__x;
    return __is;
  }
};

template <auto _Mod, unsigned _Storage>
typename modint<_Mod, _Storage>::mod_type modint<_Mod, _Storage>::mod =
    _Mod > 0 ? _Mod : 0;

template <auto _Mod, unsigned _Storage>
unsigned modint<_Mod, _Storage>::storage = _Storage;

}  // namespace _modint_impl

constexpr unsigned _modint_default_storage = 1 << 24;

template <auto _Mod, unsigned _Storage = _modint_default_storage,
          typename = std::enable_if_t<(_Mod > 0)>>
using modint = _modint_impl::modint<_Mod, _Storage>;

template <unsigned _Id = 0, unsigned _Storage = _modint_default_storage>
using runtime_modint = _modint_impl::modint<-(signed)_Id, _Storage>;

template <unsigned _Id = 0, unsigned _Storage = _modint_default_storage>
using runtime_modint64 = _modint_impl::modint<-(int_least64_t)_Id, _Storage>;

}  // namespace workspace
#line 2 "Library\\src\\data_structure\\segment_tree\\lazy.hpp"

/**
 * @file lazy.hpp
 * @brief Lazy Segment Tree
 */

#line 11 "Library\\src\\data_structure\\segment_tree\\lazy.hpp"

#line 2 "Library\\src\\algebra\\system\\monoid.hpp"

/*
 * @file monoid.hpp
 * @brief Monoid
 */

#line 9 "Library\\src\\algebra\\system\\monoid.hpp"

namespace workspace {

template <class T, class E = T> struct min_monoid {
  using value_type = T;
  static T min, max;
  T value;
  min_monoid() : value(max) {}
  min_monoid(const T &value) : value(value) {}
  operator T() const { return value; }
  min_monoid operator+(const min_monoid &rhs) const {
    return value < rhs.value ? *this : rhs;
  }
  min_monoid operator*(const E &rhs) const;
};

template <class T, class E>
T min_monoid<T, E>::min = std::numeric_limits<T>::min() / 2;
template <class T, class E>
T min_monoid<T, E>::max = std::numeric_limits<T>::max() / 2;

template <class T, class E = T> struct max_monoid : min_monoid<T, E> {
  using base = min_monoid<T, E>;
  using base::min_monoid;
  max_monoid() : base(base::min) {}
  max_monoid operator+(const max_monoid &rhs) const {
    return !(base::value < rhs.value) ? *this : rhs;
  }
  max_monoid operator*(const E &rhs) const;
};

}  // namespace workspace
#line 2 "Library\\src\\algebra\\system\\operation.hpp"

/**
 * @file operation.hpp
 * @brief Operation Traits
 */

#line 10 "Library\\src\\algebra\\system\\operation.hpp"

#line 2 "Library\\lib\\cxx17"

#line 2 "Library\\lib\\cxx14"

#ifndef _CXX14_CONSTEXPR
#if __cplusplus >= 201402L
#define _CXX14_CONSTEXPR constexpr
#else
#define _CXX14_CONSTEXPR
#endif
#endif
#line 4 "Library\\lib\\cxx17"

#ifndef _CXX17_CONSTEXPR
#if __cplusplus >= 201703L
#define _CXX17_CONSTEXPR constexpr
#else
#define _CXX17_CONSTEXPR
#endif
#endif

#ifndef _CXX17_STATIC_ASSERT
#if __cplusplus >= 201703L
#define _CXX17_STATIC_ASSERT static_assert
#else
#define _CXX17_STATIC_ASSERT assert
#endif
#endif

#line 22 "Library\\lib\\cxx17"

#if __cplusplus < 201703L

namespace std {

/**
 *  @brief  Return the size of a container.
 *  @param  __cont  Container.
 */
template <typename _Container>
constexpr auto size(const _Container& __cont) noexcept(noexcept(__cont.size()))
    -> decltype(__cont.size()) {
  return __cont.size();
}

/**
 *  @brief  Return the size of an array.
 */
template <typename _Tp, size_t _Nm>
constexpr size_t size(const _Tp (&)[_Nm]) noexcept {
  return _Nm;
}

/**
 *  @brief  Return whether a container is empty.
 *  @param  __cont  Container.
 */
template <typename _Container>
[[nodiscard]] constexpr auto empty(const _Container& __cont) noexcept(
    noexcept(__cont.empty())) -> decltype(__cont.empty()) {
  return __cont.empty();
}

/**
 *  @brief  Return whether an array is empty (always false).
 */
template <typename _Tp, size_t _Nm>
[[nodiscard]] constexpr bool empty(const _Tp (&)[_Nm]) noexcept {
  return false;
}

/**
 *  @brief  Return whether an initializer_list is empty.
 *  @param  __il  Initializer list.
 */
template <typename _Tp>
[[nodiscard]] constexpr bool empty(initializer_list<_Tp> __il) noexcept {
  return __il.size() == 0;
}

struct monostate {};

}  // namespace std

#else

#include <variant>

#endif
#line 12 "Library\\src\\algebra\\system\\operation.hpp"

namespace workspace {

// Unary `+`
template <class _Tp>
using require_unary_plus = std::enable_if_t<
    std::is_convertible<decltype(+std::declval<const _Tp &>()), _Tp>::value>;

template <class _Tp, class = void> struct has_unary_plus : std::false_type {};

template <class _Tp>
struct has_unary_plus<_Tp, require_unary_plus<_Tp>> : std::true_type {};

// Unary `-`
template <class _Tp>
using require_unary_minus = std::enable_if_t<
    std::is_convertible<decltype(-std::declval<const _Tp &>()), _Tp>::value>;

template <class _Tp, class = void> struct has_unary_minus : std::false_type {};

template <class _Tp>
struct has_unary_minus<_Tp, require_unary_minus<_Tp>> : std::true_type {};

// Binary `+`
template <class _Tp1, class _Tp2 = _Tp1>
using require_binary_plus =
    std::enable_if_t<std::is_convertible<decltype(std::declval<const _Tp1 &>() +
                                                  std::declval<const _Tp2 &>()),
                                         _Tp1>::value>;

template <class _Tp1, class _Tp2 = _Tp1, class = void>
struct has_binary_plus : std::false_type {};

template <class _Tp1, class _Tp2>
struct has_binary_plus<_Tp1, _Tp2, require_binary_plus<_Tp1, _Tp2>>
    : std::true_type {};

// Binary `-`
template <class _Tp1, class _Tp2 = _Tp1>
using require_binary_minus =
    std::__void_t<decltype(std::declval<const _Tp1 &>() -
                           std::declval<const _Tp2 &>())>;

template <class _Tp1, class _Tp2 = _Tp1, class = void>
struct has_binary_minus : std::false_type {};

template <class _Tp1, class _Tp2>
struct has_binary_minus<_Tp1, _Tp2, require_binary_minus<_Tp1, _Tp2>>
    : std::true_type {};

// Binary `*`
template <class _Tp1, class _Tp2 = _Tp1>
using require_binary_multiplies =
    std::enable_if_t<std::is_convertible<decltype(std::declval<const _Tp1 &>() *
                                                  std::declval<const _Tp2 &>()),
                                         _Tp1>::value>;

template <class _Tp1, class _Tp2 = _Tp1, class = void>
struct has_binary_multiplies : std::false_type {};

template <class _Tp1, class _Tp2>
struct has_binary_multiplies<_Tp1, _Tp2, require_binary_multiplies<_Tp1, _Tp2>>
    : std::true_type {};

// Binary `/`
template <class _Tp1, class _Tp2 = _Tp1>
using require_binary_divides =
    std::enable_if_t<std::is_convertible<decltype(std::declval<const _Tp1 &>() /
                                                  std::declval<const _Tp2 &>()),
                                         _Tp1>::value>;

template <class _Tp1, class _Tp2 = _Tp1, class = void>
struct has_binary_divides : std::false_type {};

template <class _Tp1, class _Tp2>
struct has_binary_divides<_Tp1, _Tp2, require_binary_divides<_Tp1, _Tp2>>
    : std::true_type {};

// Binary `%`
template <class _Tp1, class _Tp2 = _Tp1>
using require_binary_modulus =
    std::enable_if_t<std::is_convertible<decltype(std::declval<const _Tp1 &>() %
                                                  std::declval<const _Tp2 &>()),
                                         _Tp1>::value>;

template <class _Tp1, class _Tp2 = _Tp1, class = void>
struct has_binary_modulus : std::false_type {};

template <class _Tp1, class _Tp2>
struct has_binary_modulus<_Tp1, _Tp2, require_binary_modulus<_Tp1, _Tp2>>
    : std::true_type {};

template <class _Tp1, class _Tp2 = _Tp1, class = void, class = void,
          class = void, class = void>
struct has_arithmetic : std::false_type {};

template <class _Tp1, class _Tp2>
struct has_arithmetic<_Tp1, _Tp2, require_binary_plus<_Tp1, _Tp2>,
                      require_binary_minus<_Tp1, _Tp2>,
                      require_binary_multiplies<_Tp1, _Tp2>,
                      require_binary_divides<_Tp1, _Tp2>> : std::true_type {};

template <class _Tp1, class _Tp2 = _Tp1>
using require_arithmetic = std::enable_if_t<has_arithmetic<_Tp1, _Tp2>::value>;

// Binary `<`
template <class _Tp, class = void> struct is_comparable : std::false_type {};

template <class _Tp>
struct is_comparable<_Tp, std::__void_t<decltype(std::declval<const _Tp &>() <
                                                 std::declval<const _Tp &>())>>
    : std::true_type {};

template <class _Tp, bool _Default = false> struct try_less : std::less<_Tp> {
  constexpr bool operator()(const _Tp &__x, const _Tp &__y) noexcept {
    if _CXX17_CONSTEXPR (is_comparable<_Tp>::value)
      return std::less<_Tp>::operator()(__x, __y);
    else
      return _Default;
  }
};

}  // namespace workspace
#line 2 "Library\\src\\data_structure\\segment_tree\\waitings.hpp"

#line 5 "Library\\src\\data_structure\\segment_tree\\waitings.hpp"

namespace workspace {

namespace internal {

struct waitings : std::queue<size_t> {
  waitings(size_t n) : in(n) {}

  bool push(size_t index) {
    // assert(index < in.size());
    if (in[index]) return false;
    emplace(index);
    return (in[index] = true);
  }

  size_t pop() {
    // assert(!empty());
    auto index = front();
    std::queue<size_t>::pop();
    in[index] = false;
    return index;
  }

 private:
  std::vector<int_least8_t> in;
};

}  // namespace internal

}  // namespace workspace
#line 16 "Library\\src\\data_structure\\segment_tree\\lazy.hpp"

namespace workspace {

template <class _Monoid, class _End,
          class Monoid_container = std::vector<_Monoid>,
          class Endomorphism_container = std::vector<_End>>
class lazy_segment_tree {
  static_assert(
      std::is_same<_Monoid, typename Monoid_container::value_type>::value);

  static_assert(
      std::is_same<_End, typename Endomorphism_container::value_type>::value);

  static_assert(has_binary_plus<_Monoid>::value,
                "\'_Monoid\' has no proper binary \'operator+\'.");

  static_assert(has_binary_multiplies<_End>::value,
                "\'_End\' has no proper binary \'operator*\'.");

  static_assert(has_binary_multiplies<_Monoid, _End>::value,
                "\'_End\' is not applicable to \'_Monoid\'.");

  size_t size_orig, height, size_ext;
  Monoid_container data;
  Endomorphism_container lazy;
  internal::waitings wait;

  void repair() {
    while (!wait.empty()) {
      const size_t index = wait.pop() >> 1;
      if (index && wait.push(index)) pull(index);
    }
  }

  void apply(size_t node, const _End &endo) {
    data[node] = data[node] * endo;
    if (node < size_ext) lazy[node] = lazy[node] * endo;
  }

  void push(size_t node) {
    apply(node << 1, lazy[node]);
    apply(node << 1 | 1, lazy[node]);
    lazy[node] = _End{};
  }

  void pull(size_t node) { data[node] = data[node << 1] + data[node << 1 | 1]; }

  template <class Pred>
  static constexpr decltype(std::declval<Pred>()(_Monoid{})) pass_args(
      Pred pred, _Monoid const &_1, [[maybe_unused]] size_t _2) {
    return pred(_1);
  }

  template <class Pred>
  static constexpr decltype(std::declval<Pred>()(_Monoid{}, size_t{}))
  pass_args(Pred pred, _Monoid const &_1, size_t _2) {
    return pred(_1, _2);
  }

  template <class Pred>
  size_t left_partition_subtree(size_t node, _Monoid mono, size_t step,
                                Pred pred) {
    assert(node);
    while (node < size_ext) {
      push(node);
      const _Monoid tmp = data[(node <<= 1) | 1] + mono;
      if (pass_args(pred, tmp, ((node | 1) << --step) ^ size_ext))
        mono = tmp;
      else
        ++node;
    }
    return ++node -= size_ext;
  }

  template <class Pred>
  size_t right_partition_subtree(size_t node, _Monoid mono, size_t step,
                                 Pred pred) {
    assert(node);
    while (node < size_ext) {
      push(node);
      const _Monoid tmp = mono + data[node <<= 1];
      if (pass_args(pred, tmp, ((node | 1) << --step) ^ size_ext))
        ++node, mono = tmp;
    }
    return (node -= size_ext) < size_orig ? node : size_orig;
  }

 public:
  class iterator {
    lazy_segment_tree *__p;
    size_t __i;

   public:
    using difference_type = typename std::make_signed<size_t>::type;
    using value_type = _Monoid;
    using reference = _Monoid &;
    using pointer = iterator;
    using iterator_category = std::random_access_iterator_tag;

    /**
     * @brief Construct a new iterator object
     *
     */
    iterator() = default;

    /**
     * @brief Construct a new iterator object
     *
     * @param __p Pointer to a segment tree object
     * @param __i Index
     */
    iterator(lazy_segment_tree *__p, size_t __i) : __p(__p), __i(__i) {}

    bool operator==(iterator const &rhs) const {
      return __p == rhs.__p && __i == rhs.__i;
    }
    bool operator!=(iterator const &rhs) const { return !operator==(rhs); }

    bool operator<(iterator const &rhs) const { return __i < rhs.__i; }
    bool operator>(iterator const &rhs) const { return __i > rhs.__i; }
    bool operator<=(iterator const &rhs) const { return __i <= rhs.__i; }
    bool operator>=(iterator const &rhs) const { return __i >= rhs.__i; }

    iterator &operator++() { return ++__i, *this; }
    iterator &operator--() { return --__i, *this; }

    difference_type operator-(iterator const &rhs) const {
      return __i - rhs.__i;
    }

    /**
     * @brief
     *
     * @return reference
     */
    reference operator*() const { return __p->operator[](__i); }
  };

  using value_type = typename iterator::value_type;
  using reference = typename iterator::reference;

  iterator begin() { return {this, 0}; }
  iterator end() { return {this, size_orig}; }

  auto rbegin() { return std::make_reverse_iterator(end()); }
  auto rend() { return std::make_reverse_iterator(begin()); }

  lazy_segment_tree(size_t n = 0)
      : size_orig{n},
        height(n > 1 ? 32 - __builtin_clz(n - 1) : 0),
        size_ext{1u << height},
        data(size_ext << 1),
        lazy(size_ext),
        wait(size_ext << 1) {}

  lazy_segment_tree(size_t n, const _Monoid &init) : lazy_segment_tree(n) {
    std::fill_n(std::next(std::begin(data), size_ext), n, init);
    for (size_t i{size_ext}; --i;) pull(i);
  }

  template <class iter_type, class value_type = typename std::iterator_traits<
                                 iter_type>::value_type>
  lazy_segment_tree(iter_type first, iter_type last)
      : size_orig(std::distance(first, last)),
        height(size_orig > 1 ? 32 - __builtin_clz(size_orig - 1) : 0),
        size_ext{1u << height},
        data(size_ext << 1),
        lazy(size_ext),
        wait(size_ext << 1) {
    static_assert(std::is_constructible<_Monoid, value_type>::value,
                  "_Monoid(iter_type::value_type) is not constructible.");
    for (auto iter{std::next(std::begin(data), size_ext)};
         iter != std::end(data) && first != last; ++iter, ++first)
      *iter = _Monoid(*first);
    for (size_t i{size_ext}; --i;) pull(i);
  }

  /**
   * @return Number of elements.
   */
  size_t size() const { return size_orig; }

  /**
   * @param index Index of the element
   * @return Reference to the element.
   */
  _Monoid &operator[](size_t index) {
    assert(index < size_orig);
    index |= size_ext;
    wait.push(index);
    for (size_t i = height; i; --i) push(index >> i);
    return data[index];
  }

  void update(const _End &endo) { update(0, size_orig, endo); }

  void update(size_t index, const _End &endo) {
    update(index, index + 1, endo);
  }

  void update(size_t first, size_t last, const _End &endo) {
    assert(last <= size_orig);
    repair();
    if (first >= last) return;
    first += size_ext, last += size_ext;
    --last;
    for (size_t i = height; i; --i) push(first >> i), push(last >> i);
    ++last;
    for (size_t l = first, r = last; l != r; l >>= 1, r >>= 1) {
      if (l & 1) apply(l++, endo);
      if (r & 1) apply(--r, endo);
    }
    for (first >>= __builtin_ffs(first); first; first >>= 1) pull(first);
    for (last >>= __builtin_ffs(last); last; last >>= 1) pull(last);
  }

  /**
   * @param first Left end, inclusive
   * @param last Right end, exclusive
   * @return Sum of elements in the interval.
   */
  _Monoid fold(size_t first, size_t last) {
    assert(last <= size_orig);
    repair();
    if (first >= last) return _Monoid{};
    first += size_ext, last += size_ext - 1;
    _Monoid left_val{}, right_val{};
    for (size_t l = first, r = last + 1; l != r; l >>= 1, r >>= 1) {
      if (l & 1) left_val = left_val + data[l++];
      if (r & 1) right_val = data[--r] + right_val;
      left_val = left_val * lazy[first >>= 1];
      right_val = right_val * lazy[last >>= 1];
    }
    while (first >>= 1, last >>= 1) {
      left_val = left_val * lazy[first];
      right_val = right_val * lazy[last];
    }
    return left_val + right_val;
  }

  /**
   * @return Sum of all elements.
   */
  _Monoid fold() {
    repair();
    return data[1];
  }

  /**
   * @brief Binary search for the partition point.
   * @param right Right fixed end of the interval, exclusive
   * @param pred Predicate in the form of either 'bool(_Monoid)' or
   * 'bool(_Monoid, size_t)'
   * @return Left end of the extremal interval satisfying the condition,
   * inclusive.
   */
  template <class Pred> size_t left_partition(size_t right, Pred pred) {
    assert(right <= size_orig);
    repair();
    right += size_ext - 1;
    for (size_t i{height}; i; --i) push(right >> i);
    ++right;
    _Monoid mono{};
    for (size_t left{size_ext}, step{}; left != right;
         left >>= 1, right >>= 1, ++step) {
      if ((left & 1) != (right & 1)) {
        const _Monoid tmp = data[--right] + mono;
        if (!pass_args(pred, tmp, (right << step) ^ size_ext))
          return left_partition_subtree(right, mono, step, pred);
        mono = tmp;
      }
    }
    return 0;
  }

  /**
   * @brief Binary search for the partition point.
   * @param left Left fixed end of the interval, inclusive
   * @param pred Predicate in the form of either 'bool(_Monoid)' or
   * 'bool(_Monoid, size_t)'
   * @return Right end of the extremal interval satisfying the condition,
   * exclusive.
   */
  template <class Pred> size_t right_partition(size_t left, Pred pred) {
    assert(left <= size_orig);
    repair();
    left += size_ext;
    for (size_t i{height}; i; --i) push(left >> i);
    _Monoid mono{};
    for (size_t right{size_ext << 1}, step{}; left != right;
         left >>= 1, right >>= 1, ++step) {
      if ((left & 1) != (right & 1)) {
        const _Monoid tmp = mono + data[left];
        if (!pass_args(pred, tmp, ((left + 1) << step) ^ size_ext))
          return right_partition_subtree(left, mono, step, pred);
        mono = tmp;
        ++left;
      }
    }
    return size_orig;
  }
};

}  // namespace workspace
#line 6 "other-workspace\\749.cpp"
namespace workspace {
using mint = modint<1000000007>;
}

namespace workspace {

void main() {
  // start here!

  using mono = matrix<mint, 1, 3>;
  using endo = matrix_operator<mint, 3, 3>;

  int n, q;
  std::cin >> n >> q;
  lazy_segment_tree<mono, endo> sgt(n);
  {
    mint x, y{1};
    for (auto &e : sgt) {
      e[0][1] = x;
      e[0][2] = 1;
      x += y;
      std::swap(x, y);
    }
  }

  while (q--) {
    int t, l, r, k;
    std::cin >> t >> l >> r >> k;
    ++r;
    if (!t) {
      std::cout << sgt.fold(l, r)[0][0] * k << "\n";
      continue;
    }

    endo e;
    switch (t) {
      case 1: {
        e[0][0] = 0;
        e[2][0] = k;
      } break;

      case 2: {
        e[2][0] = k;
      } break;

      case 3: {
        e[0][0] = k;
      } break;

      case 4: {
        e[1][0] = k;
      } break;
    }
    sgt.update(l, r, e);
  }
}

}  // namespace workspace

int main() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(0);
  workspace::main();
}