#include <iostream>
#include <vector>
#include <ranges>
#include <algorithm>

#include <atcoder/modint>

/* [begin]: numeric/leveler.hpp */
#include <initializer_list>
#include <valarray>
#include <numeric>
/* [begin]: snippet/iterations.hpp */
#include <type_traits>
/* [begin]: macro/overload.hpp */
#define $OVERLOAD2(arg0, arg1, cmd, ...) cmd
#define $OVERLOAD3(arg0, arg1, arg2, cmd, ...) cmd
#define $OVERLOAD4(arg0, arg1, arg2, arg3, cmd, ...) cmd
#define $OVERLOAD5(arg0, arg1, arg2, arg3, arg4, cmd, ...) cmd
#define $OVERLOAD6(arg0, arg1, arg2, arg3, arg4, arg5, cmd, ...) cmd
/* [end]: macro/overload.hpp*/
#define LOOP(n) REPI(_$, (n))
#define REPI(i,n) for(std::decay_t<decltype(n)> i=0, i##_length=(n); i<i##_length; ++i)
#define REPF(i,l,r) for(std::common_type_t<std::decay_t<decltype(l)>,std::decay_t<decltype(r)>> i=(l), i##_last=(r); i<i##_last; ++i)
#define REPIS(i,l,r,s) for(std::common_type_t<std::decay_t<decltype(l)>,std::decay_t<decltype(r)>,std::decay_t<decltype(s)>> i=(l), i##_last=(r); i<i##_last; i+=(s))
#define REPR(i,n) for(auto i=(n); --i>=0;)
#define REPB(i,l,r) for(std::common_type_t<std::decay_t<decltype(l)>,std::decay_t<decltype(r)>> i=(r), i##_last=(l); --i>=i##_last;)
#define REPRS(i,l,r,s) for(std::common_type_t<std::decay_t<decltype(l)>,std::decay_t<decltype(r)>,std::decay_t<decltype(s)>> i=(l)+((r)-(l)-1)/(s)*(s), i##_last=(l); i>=i##_last; (i-=(s)))
#define REP(...) $OVERLOAD4(__VA_ARGS__, REPIS, REPF, REPI, LOOP)(__VA_ARGS__)
#define REPD(...) $OVERLOAD4(__VA_ARGS__, REPRS, REPB, REPR)(__VA_ARGS__)
#define FORO(i,n) for(int i=0, i##_last=static_cast<int>(n); i<=i##_last; ++i)
#define FORI(i,l,r) for(std::common_type_t<std::decay_t<decltype(l)>,std::decay_t<decltype(r)>> i=(l), i##_last=(r); i<=i##_last; ++i)
#define FORIS(i,l,r,s) for(std::common_type_t<std::decay_t<decltype(l)>,std::decay_t<decltype(r)>,std::decay_t<decltype(s)>> i=(l), i##_last=(r); i<=i##_last; i+=(s))
#define FORRO(i,n) for(auto i=(n); i>=0; --i)
#define FORR(i,l,r) for(std::common_type_t<std::decay_t<decltype(l)>,std::decay_t<decltype(r)>> i=(r), i##_last=(l); i>=i##_last; --i)
#define FORRS(i,l,r,s) for(std::common_type_t<std::decay_t<decltype(l)>,std::decay_t<decltype(r)>,std::decay_t<decltype(s)>> i=(l)+((r)-(l))/(s)*(s), i##_last=(l); i>=i##_last; i-=(s))
#define FOR(...) $OVERLOAD4(__VA_ARGS__, FORIS, FORI, FORO)(__VA_ARGS__)
#define FORD(...) $OVERLOAD4(__VA_ARGS__, FORRS, FORR, FORRO)(__VA_ARGS__)
#define ITR1(e0,v) for(const auto &e0 : (v))
#define ITRP1(e0,v) for(auto e0 : (v))
#define ITRR1(e0,v) for(auto &e0 : (v))
#define ITR2(e0,e1,v) for(const auto [e0, e1] : (v))
#define ITRP2(e0,e1,v) for(auto [e0, e1] : (v))
#define ITRR2(e0,e1,v) for(auto &[e0, e1] : (v))
#define ITR3(e0,e1,e2,v) for(const auto [e0, e1, e2] : (v))
#define ITRP3(e0,e1,e2,v) for(auto [e0, e1, e2] : (v))
#define ITRR3(e0,e1,e2,v) for(auto &[e0, e1, e2] : (v))
#define ITR4(e0,e1,e2,e3,v) for(const auto [e0, e1, e2, e3] : (v))
#define ITRP4(e0,e1,e2,e3,v) for(auto [e0, e1, e2, e3] : (v))
#define ITRR4(e0,e1,e2,e3,v) for(auto &[e0, e1, e2, e3] : (v))
#define ITR5(e0,e1,e2,e3,e4,v) for(const auto [e0, e1, e2, e3, e4] : (v))
#define ITRP5(e0,e1,e2,e3,e4,v) for(auto [e0, e1, e2, e3, e4] : (v))
#define ITRR5(e0,e1,e2,e3,e4,v) for(auto &[e0, e1, e2, e3, e4] : (v))
#define ITR(...) $OVERLOAD6(__VA_ARGS__, ITR5, ITR4, ITR3, ITR2, ITR1)(__VA_ARGS__)
#define ITRP(...) $OVERLOAD6(__VA_ARGS__, ITRP5, ITRP4, ITRP3, ITRP2, ITRP1)(__VA_ARGS__)
#define ITRR(...) $OVERLOAD6(__VA_ARGS__, ITRR5, ITRR4, ITRR3, ITRR2, ITRR1)(__VA_ARGS__)
/* [end]: snippet/iterations.hpp*/
/* [begin]: internal/types.hpp */
#include <cstdint>
namespace lib { namespace internal { using size_t = std::int64_t; using int128_t = __int128_t; using uint128_t = __uint128_t; } }
/* [end]: internal/types.hpp*/
/* [begin]: internal/dev_env.hpp */
#ifdef LOCAL_JUDGE
inline constexpr bool DEV_ENV = true; inline constexpr bool NO_EXCEPT = false;
#else
inline constexpr bool DEV_ENV = false; inline constexpr bool NO_EXCEPT = true;
#endif
#if __cplusplus >= 202100L
#define CPP20 true
#define CPP23 true
#elif __cplusplus >= 202002L
#define CPP20 true
#define CPP23 false
#else
#define CPP20 false
#define CPP23 false
#endif
/* [end]: internal/dev_env.hpp*/
/* [begin]: adaptor/valarray.hpp */
#include <cassert>
#include <iostream>
#include <algorithm>
#include <iterator>
/* [begin]: adaptor/internal/container_extender.hpp */
#include <utility>
#include <ranges>
/* [begin]: numeric/internal/mod.hpp */
/* [begin]: internal/concepts.hpp */
#include <concepts>
#include <limits>
#include <functional>
namespace lib { namespace internal { template<class Structure> concept available = requires () { typename Structure; }; template< template<class...> class Structure, class... TemplateParameters > concept available_with = available<Structure<TemplateParameters...>>; template<class T> concept arithmetic = std::is_arithmetic_v<T>; template<class T> concept pointer = std::is_pointer_v<T>; template<class T> concept structural = std::is_class_v<T>; template<class Large, class Small> concept has_double_digits_of = (std::numeric_limits<Large>::digits == 2 * std::numeric_limits<Small>::digits); template<class Large, class Small> concept has_more_digits_than = (std::numeric_limits<Large>::digits > std::numeric_limits<Small>::digits); template<class Large, class Small> concept has_or_more_digits_than = (std::numeric_limits<Large>::digits >= std::numeric_limits<Small>::digits); template<class T> concept has_static_zero = requires { T::zero; }; template<class T> concept has_static_one = requires { T::one; }; template<class L, class R = L> concept weakly_addable = requires (L lhs, R rhs) { lhs + rhs; }; template<class L, class R = L> concept weakly_subtractable = requires (L lhs, R rhs) { lhs - rhs; }; template<class L, class R = L> concept weakly_multipliable = requires (L lhs, R rhs) { lhs * rhs; }; template<class L, class R = L> concept weakly_divisable = requires (L lhs, R rhs) { lhs / rhs; }; template<class L, class R = L> concept weakly_remainder_calculable = requires (L lhs, R rhs) { lhs % rhs; }; template<class L, class R = L> concept weakly_addition_assignable = requires (L lhs, R rhs) { lhs += rhs; }; template<class L, class R = L> concept weakly_subtraction_assignable = requires (L lhs, R rhs) { lhs -= rhs; }; template<class L, class R = L> concept weakly_multipliation_assignalbe = requires (L lhs, R rhs) { lhs *= rhs; }; template<class L, class R = L> concept weakly_division_assignable = requires (L lhs, R rhs) { lhs /= rhs; }; template<class L, class R = L> concept weakly_remainder_assignable = requires (L lhs, R rhs) { lhs /= rhs; }; template<class L, class R = L> concept addable = weakly_addable<L, R> && weakly_addable<std::invoke_result_t<std::plus<>&, L, R>, R> && weakly_addable<L, std::invoke_result_t<std::plus<>&, L, R>> && weakly_addable<std::invoke_result_t<std::plus<>&, L, R>, std::invoke_result_t<std::plus<>&, L, R>>; template<class L, class R = L> concept subtractable = weakly_subtractable<L, R> && weakly_subtractable<std::invoke_result_t<std::minus<>&, L, R>, R> && weakly_subtractable<L, std::invoke_result_t<std::minus<>&, L, R>> && weakly_subtractable<std::invoke_result_t<std::minus<>&, L, R>, std::invoke_result_t<std::minus<>&, L, R>>; template<class L, class R = L> concept multipliable = weakly_multipliable<L, R> && weakly_multipliable<std::invoke_result_t<std::multiplies<>&, L, R>, R> && weakly_multipliable<L, std::invoke_result_t<std::multiplies<>&, L, R>> && weakly_multipliable<std::invoke_result_t<std::multiplies<>&, L, R>, std::invoke_result_t<std::multiplies<>&, L, R>>; template<class L, class R = L> concept divisable = weakly_divisable<L, R> && weakly_divisable<std::invoke_result_t<std::divides<>&, L, R>, R> && weakly_divisable<L, std::invoke_result_t<std::divides<>&, L, R>> && weakly_divisable<std::invoke_result_t<std::divides<>&, L, R>, std::invoke_result_t<std::divides<>&, L, R>>; template<class L, class R = L> concept remainder_calculable = weakly_remainder_calculable<L, R> && weakly_remainder_calculable<std::invoke_result_t<std::modulus<>&, L, R>, R> && weakly_remainder_calculable<L, std::invoke_result_t<std::modulus<>&, L, R>> && weakly_remainder_calculable<std::invoke_result_t<std::modulus<>&, L, R>, std::invoke_result_t<std::modulus<>&, L, R>>; template<class L, class R = L> concept addition_assignable = weakly_addition_assignable<L, R> && weakly_addition_assignable<std::decay_t<std::invoke_result_t<std::plus<>&, L, R>>, R> && weakly_addition_assignable<L, std::invoke_result_t<std::plus<>&, L, R>> && weakly_addition_assignable<std::decay_t<std::invoke_result_t<std::plus<>&, L, R>>, std::invoke_result_t<std::plus<>&, L, R>>; template<class L, class R = L> concept subtraction_assignable = weakly_subtraction_assignable<L, R> && weakly_subtraction_assignable<std::decay_t<std::invoke_result_t<std::minus<>&, L, R>>, R> && weakly_subtraction_assignable<L, std::invoke_result_t<std::minus<>&, L, R>> && weakly_subtraction_assignable<std::decay_t<std::invoke_result_t<std::minus<>&, L, R>>, std::invoke_result_t<std::minus<>&, L, R>>; template<class L, class R = L> concept multipliation_assignalbe = weakly_multipliation_assignalbe<L, R> && weakly_multipliation_assignalbe<std::decay_t<std::invoke_result_t<std::multiplies<>&, L, R>>, R> && weakly_multipliation_assignalbe<L, std::invoke_result_t<std::multiplies<>&, L, R>> && weakly_multipliation_assignalbe<std::decay_t<std::invoke_result_t<std::multiplies<>&, L, R>>, std::invoke_result_t<std::multiplies<>&, L, R>>; template<class L, class R = L> concept division_assignable = weakly_division_assignable<L, R> && weakly_division_assignable<std::decay_t<std::invoke_result_t<std::divides<>&, L, R>>, R> && weakly_division_assignable<L, std::invoke_result_t<std::divides<>&, L, R>> && weakly_division_assignable<std::decay_t<std::invoke_result_t<std::divides<>&, L, R>>, std::invoke_result_t<std::divides<>&, L, R>>; template<class L, class R = L> concept remainder_assignable = weakly_remainder_assignable<L, R> && weakly_remainder_assignable<std::decay_t<std::invoke_result_t<std::modulus<>&, L, R>>, R> && weakly_remainder_assignable<L, std::invoke_result_t<std::modulus<>&, L, R>> && weakly_remainder_assignable<std::decay_t<std::invoke_result_t<std::modulus<>&, L, R>>, std::invoke_result_t<std::modulus<>&, L, R>>; template<class T> concept weakly_incrementable = std::movable<T> && requires (T v) { { ++v } -> std::same_as<T&>; v++; }; template<class T> concept weakly_decrementable = std::movable<T> && requires (T v) { { --v } -> std::same_as<T&>; v--; }; template<class T> concept incrementable = std::regular<T> && weakly_incrementable<T> && requires (T v) { { v++ } -> std::same_as<T>; }; template<class T> concept decrementable = std::regular<T> && weakly_decrementable<T> && requires (T v) { { v-- } -> std::same_as<T>; }; template<class L, class R = L> concept weakly_arithmetic_operable = weakly_addable<L, R> && weakly_subtractable<L, R> && weakly_multipliable<L, R> && weakly_divisable<L, R>; template<class L, class R = L> concept weakly_arithmetic_operation_assignable = weakly_addition_assignable<L, R> && weakly_subtraction_assignable<L, R> && weakly_multipliation_assignalbe<L, R> && weakly_division_assignable<L, R>; template<class L, class R = L> concept arithmetic_operable = weakly_arithmetic_operable<L, R> && addable<L, R> && subtractable<L, R> && multipliable<L, R> && divisable<L, R>; template<class L, class R = L> concept arithmetic_operation_assignable = weakly_arithmetic_operation_assignable<L, R> && addition_assignable<L, R> && subtraction_assignable<L, R> && multipliation_assignalbe<L, R> && division_assignable<L, R>; template<class T> concept unary_addable = requires (T v) { { +v } -> std::same_as<T>; }; template<class T> concept unary_subtractable = requires (T v) { { -v } -> std::same_as<T>; }; template<class T> concept numeric = std::regular<T> && arithmetic_operable<T> && arithmetic_operation_assignable<T> && weakly_incrementable<T> && unary_addable<T> && unary_subtractable<T>; } }
/* [end]: internal/concepts.hpp*/
namespace lib { template<class T, class R> requires internal::remainder_calculable<T, R> && internal::subtractable<T, R> && internal::unary_subtractable<T> inline T mod(T x, const R& r) noexcept(NO_EXCEPT) { if(x >= 0) return x % r; x = -x % r; if(x != 0) x = r - x; return x; } }
/* [end]: numeric/internal/mod.hpp*/
/* [begin]: iterable/internal/operation_base.hpp */
#include <sstream>
/* [begin]: snippet/aliases.hpp */
#include <vector>
/* [begin]: snippet/internal/types.hpp */
namespace lib { using i16 = std::int16_t; using u16 = std::uint16_t; using i32 = std::int32_t; using u32 = std::uint32_t; using i64 = std::int64_t; using u64 = std::uint64_t;
#ifdef __GNUC__
using i128 = __int128_t; using u128 = __uint128_t;
#endif
using uint = unsigned; using ll = long long; using ull = unsigned long long; using ld = long double; }
/* [end]: snippet/internal/types.hpp*/
#define until(...) while(!(__VA_ARGS__))
#define CONTINUE(...) { __VA_ARGS__; continue; }
#define BREAK(...) { __VA_ARGS__; break; }
#define ALL(x) std::ranges::begin((x)),std::ranges::end((x))
#define RALL(x) std::ranges::rbegin((x)),std::ranges::rend((x))
#define $F first
#define $S second
namespace lib { constexpr char LN = '\n'; constexpr char SPC = ' '; constexpr std::pair<int,int> DIRS4[] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } }; constexpr std::pair<int,int> DIRS4P[] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 }, { 0, 0 } }; constexpr std::pair<int,int> DIRS8[] = { { -1, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 }, { 1, 0 }, { 1, -1 }, { 0, -1 }, { -1, -1 } }; constexpr std::pair<int,int> DIRS8P[] = { { -1, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 }, { 1, 0 }, { 1, -1 }, { 0, -1 }, { -1, -1 }, { 0, 0 } }; template<class T> using spair = std::pair<T,T>; } namespace std { using bit_reference = std::vector<bool>::reference; bit_reference operator |= (bit_reference a, const bool b) noexcept(NO_EXCEPT) { return a = a | b; } bit_reference operator &= (bit_reference a, const bool b) noexcept(NO_EXCEPT) { return a = a & b; } }
/* [end]: snippet/aliases.hpp*/
namespace lib { template<std::input_iterator I, std::sentinel_for<I> S> std::string join(I first, S last, const char* sep = "") noexcept(NO_EXCEPT) { if(first == last) return ""; std::ostringstream res; while(true) { res << *first; std::ranges::advance(first, 1); if(first == last) break; res << sep; } return res.str(); } template<std::ranges::input_range R> std::string join(R&& range, const char* sep = "") noexcept(NO_EXCEPT) { return join(ALL(range), sep); } }
/* [end]: iterable/internal/operation_base.hpp*/
namespace lib { namespace internal { template<class Base> struct extended_container : Base { private: inline Base* _base() noexcept(NO_EXCEPT) { return static_cast<Base*>(this); } inline const Base* _base() const noexcept(NO_EXCEPT) { return static_cast<const Base*>(this); } public: using Base::Base; extended_container(const Base& base) : Base(base) {} using size_type = decltype(std::ranges::size(std::declval<Base>())); using value_type = typename Base::value_type; inline auto ssize() const noexcept(NO_EXCEPT) { return std::ranges::ssize(*this); } inline const auto& operator[](internal::size_t p) const noexcept(NO_EXCEPT) { p = p < 0 ? p + this->size() : p; assert(0 <= p && p < static_cast<internal::size_t>(this->size())); return this->Base::operator[](p); } inline auto& operator[](internal::size_t p) noexcept(NO_EXCEPT) { p = p < 0 ? p + this->size() : p; assert(0 <= p && p < static_cast<internal::size_t>(this->size())); return this->Base::operator[](p); } inline auto& fill(const value_type& v) noexcept(NO_EXCEPT) { std::ranges::fill(*this->_base(), v); return *this; } inline auto& swap(const size_type i, const size_type j) noexcept(NO_EXCEPT) { std::swap(this->operator[](i), this->operator[](j)); return *this; } inline auto& sort() noexcept(NO_EXCEPT) { std::ranges::sort(*this->_base()); return *this; } template<class F> inline auto& sort(const F& f) noexcept(NO_EXCEPT) { std::ranges::sort(*this->_base(), f); return *this; } inline auto& stable_sort() noexcept(NO_EXCEPT) { std::ranges::stable_sort(*this->_base()); return *this; } template<class F> inline auto& stable_sort(const F& f) noexcept(NO_EXCEPT) { std::ranges::stable_sort(*this->_base(), f); return *this; } inline auto& reverse() noexcept(NO_EXCEPT) { std::ranges::reverse(*this->_base()); return *this; } inline auto count(const value_type& v) const noexcept(NO_EXCEPT) { return std::ranges::count(*this->_base(), v); } template<class F> inline auto count_if(F& f) const noexcept(NO_EXCEPT) { return std::ranges::count_if(*this->_base(), f); } inline auto& resize(const size_type k) noexcept(NO_EXCEPT) { this->Base::resize(k); return *this; } inline auto& resize(const size_type k, const value_type v) noexcept(NO_EXCEPT) { this->Base::resize(k, v); return *this; } template<class F> inline auto& shuffle(const F& f) noexcept(NO_EXCEPT) { std::ranges::shuffle(*this->_base(), f); return *this; } inline auto& unique() noexcept(NO_EXCEPT) { const auto rest = std::ranges::unique(*this->_base()); this->erase(ALL(rest)); return *this; } template<class T> inline auto binary_search(const T& v) noexcept(NO_EXCEPT) { return std::ranges::binary_search(*this->_base(), v); } template<class T> inline auto lower_bound(const T& v) noexcept(NO_EXCEPT) { return std::ranges::lower_bound(*this->_base(), v); } template<class T> inline auto upper_bound(const T& v) noexcept(NO_EXCEPT) { return std::ranges::upper_bound(*this->_base(), v); } inline auto join(const char* sep = "") noexcept(NO_EXCEPT) { return lib::join(*this->_base(), sep); } }; } }
/* [end]: adaptor/internal/container_extender.hpp*/
namespace lib { template<class T> struct valarray : internal::extended_container<std::valarray<T>> { private: using base = internal::extended_container<std::valarray<T>>; public: using size_type = internal::size_t; using iterator = T*; using const_iterator = const T*; protected: inline bool _validate_index_in_right_open([[maybe_unused]] const size_type p) const noexcept(NO_EXCEPT) { return 0 <= p and p < this->size(); } inline bool _validate_index_in_closed([[maybe_unused]] const size_type p) const noexcept(NO_EXCEPT) { return 0 <= p and p <= this->size(); } inline bool _validate_rigth_open_interval([[maybe_unused]] const size_type l, [[maybe_unused]] const size_type r) const noexcept(NO_EXCEPT) { return 0 <= l and l <= r and r <= this->size(); } inline size_type _positivize_index(const size_type p) const noexcept(NO_EXCEPT) { return p < 0 ? this->size() + p : p; } public: valarray() noexcept(NO_EXCEPT) {} explicit valarray(const std::size_t length, const T& val = T{}) noexcept(NO_EXCEPT) : base(std::forward<const T>(val), length) {} template<std::input_iterator I, std::sentinel_for<I> S> valarray(I first, S last) noexcept(NO_EXCEPT) : base(std::ranges::distance(first, last)) { std::ranges::copy(first, last, std::ranges::begin(*this)); } template<class U> valarray(const U* pointer, const size_t n) noexcept(NO_EXCEPT) : base(pointer, n) {}; valarray(const std::slice_array<T>& arr) noexcept(NO_EXCEPT) : base(arr) {}; valarray(const std::gslice_array<T>& arr) noexcept(NO_EXCEPT) : base(arr) {}; valarray(const std::mask_array<T>& arr) noexcept(NO_EXCEPT) : base(arr) {}; valarray(const std::indirect_array<T>& arr) noexcept(NO_EXCEPT) : base(arr) {}; valarray(const std::initializer_list<T>& init) noexcept(NO_EXCEPT) : base(init) {}
#ifdef __GNUC__
template<class Dom> valarray(const std::_Expr<Dom,T>& expr) noexcept(NO_EXCEPT) : base(expr) {}
#endif
inline auto size() const noexcept(NO_EXCEPT) { return static_cast<size_type>(this->base::size()); } inline void reserve(const size_type) noexcept(NO_EXCEPT) { /* do nothing */ } template<std::input_iterator I, std::sentinel_for<I> S> inline void assign(I first, S last) noexcept(NO_EXCEPT) { this->resize(std::ranges::distance(first, last)); std::ranges::copy(first, last, std::ranges::begin(*this)); } inline void assign(const std::size_t length, const T& val = T{}) noexcept(NO_EXCEPT) { this->base::resize(length, val); } inline void resize(const std::size_t length, const T& val = T{}) noexcept(NO_EXCEPT) { base temp = *this; this->assign(length, val); std::move(std::begin(temp), std::min(std::end(temp), std::next(std::begin(temp), length)), std::begin(*this)); } inline const T& operator[](size_type pos) const noexcept(NO_EXCEPT) { pos = this->_positivize_index(pos), assert(this->_validate_index_in_right_open(pos)); return this->base::operator[](pos); } inline T& operator[](size_type pos) noexcept(NO_EXCEPT) { pos = this->_positivize_index(pos), assert(this->_validate_index_in_right_open(pos)); return this->base::operator[](pos); } inline const T& back() const noexcept(NO_EXCEPT) { return *std::prev(this->end()); } inline T& back() noexcept(NO_EXCEPT) { return *std::prev(this->end()); } inline const T& front() const noexcept(NO_EXCEPT) { return *this->begin(); } inline T& front() noexcept(NO_EXCEPT) { return *this->begin(); } inline const T* begin() const noexcept(NO_EXCEPT) { return this->size() ? std::addressof((*this)[0]) : nullptr; } inline T* begin() noexcept(NO_EXCEPT) { return this->size() ? std::addressof((*this)[0]) : nullptr; } inline const T* end() const noexcept(NO_EXCEPT) { if(auto n = this->size()) { return std::addressof((*this)[0]) + n; } else { return nullptr; } } inline T* end() noexcept(NO_EXCEPT) { if(auto n = this->size()) { return std::addressof((*this)[0]) + n; } else { return nullptr; } } inline auto rbegin() noexcept(NO_EXCEPT) { return std::make_reverse_iterator(std::end(*this)); } inline auto rend() noexcept(NO_EXCEPT) { return std::make_reverse_iterator(std::begin(*this)); } inline auto rbegin() const noexcept(NO_EXCEPT) { return std::make_reverse_iterator(std::end(*this)); } inline auto rend() const noexcept(NO_EXCEPT) { return std::make_reverse_iterator(std::begin(*this)); } }; }
/* [end]: adaptor/valarray.hpp*/
namespace lib { template<class T = internal::size_t> struct leveler { using value_type = T; using size_type = internal::size_t; private: lib::valarray<value_type> _bases; size_type _dim; value_type _max; inline value_type _compute_max() const noexcept(NO_EXCEPT) { return std::reduce(std::begin(this->_bases), std::end(this->_bases), 1, std::multiplies<value_type>{}); } public: leveler(const std::initializer_list<value_type> bases) noexcept(NO_EXCEPT) : _bases(bases), _dim(std::ranges::size(bases)) { this->_max = this->_compute_max(); } template<class I> leveler(I first, I last) noexcept(NO_EXCEPT) : _bases(first, last), _dim(std::distance(first, last)) { this->_max = this->_compute_max(); } template<std::ranges::forward_range R> leveler(R&& range) noexcept(NO_EXCEPT) : leveler(std::ranges::begin(range), std::ranges::end(range)) {} template<std::integral... Values> leveler(const Values... bases) noexcept(NO_EXCEPT) : leveler(std::initializer_list<value_type>{ bases... }) {} inline size_type dimension() const noexcept(NO_EXCEPT) { return this->_dim; } inline value_type sup() const noexcept(NO_EXCEPT) { return this->_max; } inline value_type convert(const std::initializer_list<value_type> inds) const noexcept(NO_EXCEPT) { return this->convert(inds | std::views::all); } template<std::ranges::forward_range R> inline value_type convert(R&& range) const noexcept(NO_EXCEPT) { assert(std::ranges::distance(range) == std::ranges::ssize(this->_bases)); value_type res = 0; { auto size = std::ranges::begin(this->_bases); ITR(v, range) { assert(0 <= v and v < *size); res *= *(size++); res += v; } } return res; } template<std::integral... Values> inline value_type convert(const Values... inds) const noexcept(NO_EXCEPT) { return this->convert({ inds... }); } inline lib::valarray<value_type> revert(value_type id) const noexcept(NO_EXCEPT) { assert(0 <= id and id < this->sup()); lib::valarray<value_type> res(std::size(this->_bases)); REPD(i, std::size(this->_bases)) { res[i] = id % this->_bases[i]; id /= this->_bases[i]; } return res; } auto _debug() const { return this->_bases; } }; }
/* [end]: numeric/leveler.hpp*/
/* [begin]: template/debug.hpp */
/* [begin]: debugger/debug.hpp */
#include <array>
#include <string>
#include <cstring>
#include <bitset>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <iomanip>
/* [begin]: numeric/int128.hpp */
#include <cctype>
namespace std { template<class C, class S> basic_istream<C,S>& operator>>(std::basic_istream<C,S>& in, lib::i128& v) noexcept(NO_EXCEPT) { std::string str; in >> str; v = 0; bool negative = (str[0] == '-'); REP(d, std::next(str.begin(), negative), str.end()) { assert(std::isdigit(*d)); v = v * 10 + *d - '0'; } if(negative) v *= -1; return in; } template<class C, class S> basic_istream<C,S>& operator>>(std::basic_istream<C,S>& in, lib::u128& v) noexcept(NO_EXCEPT) { std::string str; in >> str; v = 0U; assert(str[0] != '-'); REP(d, str.begin(), str.end()) { assert(std::isdigit(*d)); v = v * 10U + *d - '0'; } return in; } template<class C, class S> basic_ostream<C,S>& operator<<(std::basic_ostream<C,S>& out, lib::i128 v) noexcept(NO_EXCEPT) { if(v == 0) return out << 0; if(v < 0) out << '-', v *= -1; std::string str; while(v > 0) str += static_cast<char>(v%10) + '0', v /= 10; std::reverse(str.begin(), str.end()); return out << str; } template<class C, class S> basic_ostream<C,S>& operator<<(std::basic_ostream<C,S>& out, lib::u128 v) noexcept(NO_EXCEPT) { if(v == 0) return out << 0U; std::string str; while(v > 0) str += static_cast<char>(v%10U) + '0', v /= 10U; std::reverse(str.begin(), str.end()); return out << str; } }
/* [end]: numeric/int128.hpp*/
/* [begin]: internal/type_traits.hpp */
namespace lib { namespace internal { template<class... Ts> struct tuple_or_pair { using type = std::tuple<Ts...>; }; template<class T, class U> struct tuple_or_pair<T,U> { using type = std::pair<T, U>; }; template <class... Ts> using tuple_or_pair_t = typename tuple_or_pair<Ts...>::type; template<class T> constexpr std::underlying_type_t<T> to_underlying(const T& v) noexcept(NO_EXCEPT) { return static_cast<std::underlying_type_t<T>>(v); } template<class T, class... Ts> using are_same = std::conjunction<std::is_same<T, Ts>...>; template<class T, class... Ts> inline constexpr bool are_same_v = are_same<T, Ts...>::value; template<class T, class... Ts> using is_same_as_any_of = std::disjunction<std::is_same<T, Ts>...>; template<class T, class... Ts> inline constexpr bool is_same_as_any_of_v = is_same_as_any_of<T, Ts...>::value; template<class T, class... Ts> concept same_as_any_of = is_same_as_any_of_v<T, Ts...>; template<class Base, class... Derived> using is_base_of_all = std::conjunction<std::is_base_of<Base, Derived>...>; template<class Base, class... Derived> inline constexpr bool is_base_of_all_v = is_base_of_all<Base, Derived...>::value; template<class Base, class... Derived> using is_base_of_any = std::disjunction<std::is_base_of<Base, Derived>...>; template<class Base, class... Derived> inline constexpr bool is_base_of_any_v = is_base_of_any<Base, Derived...>::value; template<class T> struct remove_cvref { using type = typename std::remove_cv_t<std::remove_reference_t<T>>; }; template<class T> using remove_cvref_t = typename remove_cvref<T>::type; template<class T> struct literal_operator { static constexpr const char* value = ""; }; template<> struct literal_operator<unsigned> { static constexpr const char* value = "U"; }; template<> struct literal_operator<long> { static constexpr const char* value = "L"; }; template<> struct literal_operator<unsigned long> { static constexpr const char* value = "UL"; }; template<> struct literal_operator<long long> { static constexpr const char* value = "LL"; }; template<> struct literal_operator<unsigned long long> { static constexpr const char* value = "ULL"; }; template<> struct literal_operator<float> { static constexpr const char* value = "F"; }; template<> struct literal_operator<double> { static constexpr const char* value = "D"; }; template<> struct literal_operator<long double> { static constexpr const char* value = "LD"; };
#ifdef __SIZEOF_INT128__
template<> struct literal_operator<__int128_t> { static constexpr const char* value = "LLL"; }; template<> struct literal_operator<__uint128_t> { static constexpr const char* value = "ULLL"; };
#endif
template<class T> inline constexpr auto literal_operator_v = literal_operator<T>::value; template <std::size_t N, typename... Types> struct nth_type {}; template <class Head, class... Tail> struct nth_type<0, Head, Tail...> { using type = Head; }; template <std::size_t N, class Head, class... Tail> struct nth_type<N, Head, Tail...> : public nth_type<N - 1, Tail...> {}; template <std::size_t N, typename... Types> using nth_type_t = typename nth_type<N, Types...>::type; template<template <class...> class, class> struct is_template_of : std::false_type {}; template<template <class...> class Template, class... Args> struct is_template_of<Template, Template<Args...>> : std::true_type {}; template<template <class...> class Template, class Type> inline constexpr bool is_template_of_v = is_template_of<Template, Type>::value; template<class Type, template <class...> class Template> concept substituted_from = is_template_of_v<Template, Type>; template<template <class...> class Base, class Derived> struct _is_basic_tempalte_of { template<class... Ts> static constexpr std::true_type test(const Base<Ts...> *); static constexpr std::false_type test(...); using type = decltype(test(std::declval<Derived*>())); }; template<template <class...> class Base, class Derived> using is_basic_tempalte_of = _is_basic_tempalte_of<Base, Derived>::type; template<template <class...> class Base, class Derived> inline constexpr bool is_basic_tempalte_of_v = is_basic_tempalte_of<Base, Derived>::value; template<class Derived, template <class...> class Base> concept derived_from_template = is_basic_tempalte_of_v<Base, Derived>; template<class T> struct is_loggable { template<class U> static constexpr auto External(U &&v) -> decltype(_debug(v), std::true_type()); static constexpr std::false_type External(...); template<class U> static constexpr auto Member(U &&v) -> decltype(v._debug(), std::true_type()); static constexpr std::false_type Member(...); static constexpr bool value = ( decltype(External(std::declval<T>()))::value || decltype(Member(std::declval<T>()))::value ); }; template<class T> inline constexpr auto is_loggable_v = is_loggable<T>::value; template<class T> concept loggable = is_loggable_v<T>; template<class T> struct _has_iterator { template<class U> static constexpr auto ADL(U &&v) -> decltype(begin(v), end(v), std::true_type()); static constexpr std::false_type ADL(...); template<class U> static constexpr auto STL(U &&v) -> decltype(std::begin(v), std::end(v), std::true_type()); static constexpr std::false_type STL(...); template<class U> static constexpr auto Member(U &&v) -> decltype(v.begin(), v.end(), std::true_type()); static constexpr std::false_type Member(...); }; template<class T> struct has_iterator { struct ADL : decltype(_has_iterator<T>::ADL(std::declval<T>())) {}; struct STL : decltype(_has_iterator<T>::STL(std::declval<T>())) {}; struct Member : decltype(_has_iterator<T>::Member(std::declval<T>())) {}; static constexpr auto adl_v = ADL::value; static constexpr auto stl_v = STL::value; static constexpr auto member_v = Member::value; }; template<class T> struct is_iterable { static constexpr bool value = has_iterator<T>::adl_v || has_iterator<T>::stl_v || has_iterator<T>::member_v; }; template<class T> inline constexpr auto is_iterable_v = is_iterable<T>::value; template<class T> concept iterable = is_iterable_v<T>; namespace iterator_resolver { template<class T> inline constexpr auto begin(T&& v) noexcept(NO_EXCEPT) { static_assert(is_iterable_v<T>); if constexpr(has_iterator<T>::member_v) { return v.begin(); } else { using std::begin; return begin(std::forward<T>(v)); } } template<class T> inline constexpr auto end(T&& v) noexcept(NO_EXCEPT) { static_assert(is_iterable_v<T>); if constexpr(has_iterator<T>::member_v) { return v.end(); } else { using std::end; return end(std::forward<T>(v)); } } }; template<class C> using iterator_t = decltype(iterator_resolver::begin(std::declval<C&>())); template<class C> using container_size_t = decltype(std::size(std::declval<C&>())); template<bool Const, class T> using maybe_const_t = std::conditional_t<Const, const T, T>; template<class T> using with_ref = T&; template<class T> concept can_reference = requires { typename with_ref<T>; }; } }
/* [end]: internal/type_traits.hpp*/
/* [begin]: internal/resolving_rank.hpp */
namespace lib { namespace internal { template<int P> struct resolving_rank : resolving_rank<P-1> {}; template<> struct resolving_rank<0> {}; } }
/* [end]: internal/resolving_rank.hpp*/
/* [begin]: internal/exception.hpp */
namespace lib { namespace internal { template<class... T> inline constexpr bool EXCEPTION = false; template<const int T> inline constexpr bool EXCEPTION_INT = false; } }
/* [end]: internal/exception.hpp*/
#include <typeinfo>
#include <cxxabi.h>
namespace debugger { template<class T> auto _debug (T&& val) -> decltype(val._debug()) { return val._debug(); } std::ostream *cdebug = &std::clog; const std::string COLOR_INIT = "\033[m"; const std::string COLOR_STRING = "\033[33m"; const std::string COLOR_TYPE = "\033[34m"; const std::string COLOR_NUMERIC = "\033[36m"; const std::string COLOR_LITERAL_OPERATOR = "\033[31m"; using Brackets = std::pair<std::string, std::string>; template<class T> std::string dump(T&&); template<class T> const std::string get_type_name(T&& val) { const char* const name = typeid(std::forward<T>(val)).name(); int status = -4; char* const demangled_name = abi::__cxa_demangle(name, NULL, NULL, &status); std::string res{name}; if (status == 0) { res = std::string(demangled_name); free(demangled_name); } return COLOR_TYPE + res + COLOR_INIT; } struct debug_t : std::string { using std::string::string; debug_t(const std::string& str) { this->assign(str); } }; template<size_t N, class T> void dump_tuple_impl([[maybe_unused]] T&& val, std::stringstream &res) { if constexpr(N < std::tuple_size_v<std::decay_t<T>>) { res << dump(std::get<N>(val)); if constexpr(N < std::tuple_size_v<std::decay_t<T>> - 1) res << ", "; dump_tuple_impl<N + 1>(std::forward<T>(val), res); } } template<std::ranges::input_range R> std::string dump_range_impl(R&& range, const Brackets& brcs = { "[", "]" }, const std::string& spl = ", ") { std::stringstream res; res << brcs.first << " "; auto itr = std::ranges::begin(range); auto end = std::ranges::end(std::forward<R>(range)); while(itr != end) { if(std::ranges::next(itr) == end) res << dump(*itr) << " "; else res << dump(*itr) << spl; ++itr; } res << brcs.second ; return res.str(); } std::string dump_debug_t(debug_t info) { return info; } struct dump_primitive_like { std::string operator()(std::nullptr_t) const { return COLOR_INIT; } template<lib::internal::pointer T> std::string operator()(const T ptr) const { return dump(*ptr); } template<class T> requires lib::internal::derived_from_template<std::decay_t<T>, std::basic_string> std::string operator()(T&& val) const { std::stringstream res; res << COLOR_STRING << "`" << val << "`" << COLOR_INIT; return res.str(); } std::string operator()(const char val) const { std::stringstream res; res << COLOR_STRING << "\'" << val << "\'" << COLOR_INIT; return res.str(); } std::string operator()(const char val[]) const { std::stringstream res; res << COLOR_STRING << "\"" << val << "\"" << COLOR_INIT; return res.str(); } std::string operator()(const unsigned char val) const { std::stringstream res; res << COLOR_NUMERIC << static_cast<int>(val) << COLOR_INIT; return res.str(); } std::string operator()(const bool val) const { std::stringstream res; res << COLOR_NUMERIC << (val ? "true" : "false" ) << COLOR_INIT; return res.str(); } template<lib::internal::arithmetic T> std::string operator()(const T val) const { std::stringstream res; res << COLOR_NUMERIC << std::setprecision(std::numeric_limits<T>::digits10); res << val << COLOR_LITERAL_OPERATOR << lib::internal::literal_operator_v<T>; res << COLOR_INIT; return res.str(); }; template<class T> requires lib::internal::derived_from_template<std::decay_t<T>, std::optional> std::string operator()(T&& val) const { if(val.has_value()) return dump(*val); return COLOR_TYPE + "invalid" + COLOR_INIT; } }; struct dump_bitset { template<std::size_t N> std::string operator()(const std::bitset<N>& val) const { std::stringstream res; res << COLOR_NUMERIC << val.to_string() << COLOR_INIT; return res.str(); } }; struct dump_has_val { template<class T> requires requires (T val) { val.val(); } std::string operator()(T&& val) const { return dump(val.val()); } }; struct dump_iterator { template<std::input_or_output_iterator I> std::string operator()(I&& itr) const { return COLOR_TYPE + "<iterator> " + COLOR_INIT+ dump(*itr); } }; struct dump_wrapper { template<class T> requires lib::internal::derived_from_template<std::decay_t<T>, std::map> std::string operator()(T&& val) const { return dump_range_impl(val, Brackets("{", "}")); } template<class T> requires lib::internal::derived_from_template<std::decay_t<T>, std::multimap> std::string operator()(T&& val) const { return dump_range_impl(val, Brackets("{", "}")); } template<class T> requires lib::internal::derived_from_template<std::decay_t<T>, std::unordered_map> std::string operator()(T&& val) const { return dump_range_impl(val, Brackets("{", "}")); } template<class T> requires lib::internal::derived_from_template<std::decay_t<T>, std::unordered_multimap> std::string operator()(T&& val) const { return dump_range_impl(val, Brackets("{", "}")); } template<class T> requires lib::internal::derived_from_template<std::decay_t<T>, std::set> std::string operator()(T&& val) const { return dump_range_impl(val, Brackets("{", "}")); } template<class T> requires lib::internal::derived_from_template<std::decay_t<T>, std::multiset> std::string operator()(T&& val) const { return dump_range_impl(val, Brackets("{", "}")); } template<class T> requires lib::internal::derived_from_template<std::decay_t<T>, std::unordered_set> std::string operator()(T&& val) const { return dump_range_impl(val, Brackets("{", "}")); } template<class T> requires lib::internal::derived_from_template<std::decay_t<T>, std::unordered_multiset> std::string operator()(T&& val) const { return dump_range_impl(val, Brackets("{", "}")); } template<class T> requires lib::internal::derived_from_template<std::decay_t<T>, std::vector> std::string operator()(T&& val) const { return dump_range_impl(val, Brackets("[", "]")); } template<class T> requires lib::internal::derived_from_template<std::decay_t<T>, std::deque> std::string operator()(T&& val) const { return dump_range_impl(val, Brackets("[", "]")); } template<lib::internal::derived_from_template<std::queue> T> std::string operator()(T val) const { std::vector<typename T::value_type> vec; while(!val.empty()) vec.emplace_back(val.front()), val.pop(); return dump_range_impl(vec, Brackets("<", ">")); } template<lib::internal::derived_from_template<std::stack> T> std::string operator()(T val) const { std::vector<typename T::value_type> vec; while(!val.empty()) vec.emplace_back(val.top()), val.pop(); std::ranges::reverse(vec); return dump_range_impl(vec, Brackets("<", ">")); } template<lib::internal::derived_from_template<std::priority_queue> T> std::string operator()(T val) const { std::vector<typename T::value_type> vec; while(!val.empty()) vec.emplace_back(val.top()), val.pop(); return dump_range_impl(vec, Brackets("<", ">")); } template<class T> requires lib::internal::derived_from_template<std::decay_t<T>, std::pair> std::string operator()(T&& val) const { std::stringstream res; res << "( " << dump(val.first) << ", " << dump(val.second) << " )"; return res.str(); } template<class T> requires lib::internal::derived_from_template<std::decay_t<T>, std::tuple> std::string operator()(T&& val) const { std::stringstream res; res << "( "; dump_tuple_impl<0>(val, res); res << " )"; return res.str(); } }; struct dump_range { template<std::ranges::input_range T> std::string operator()(T&& val) const { return dump_range_impl(val); } }; struct dump_loggable { template<lib::internal::loggable T> std::string operator()(T&& val) const { auto res = _debug(val); if constexpr(std::same_as<decltype(res), debug_t>) { return res; } else { return dump(res); } } }; template<class T> std::string dump(T&& val) { if constexpr(std::same_as<std::remove_cvref_t<T>, debug_t>) { return dump_debug_t(std::forward<T>(val)); } if constexpr(std::invocable<dump_primitive_like, T>) { return dump_primitive_like{}(std::forward<T>(val)); } if constexpr(std::invocable<dump_loggable, T>) { return dump_loggable{}(std::forward<T>(val)); } if constexpr(std::invocable<dump_has_val, T>) { return dump_has_val{}(std::forward<T>(val)); } if constexpr(std::invocable<dump_bitset, T>) { return dump_bitset{}(std::forward<T>(val)); } if constexpr(std::invocable<dump_iterator, T>) { return dump_iterator{}(std::forward<T>(val)); } if constexpr(std::invocable<dump_wrapper, T>) { return dump_wrapper{}(std::forward<T>(val)); } if constexpr(std::invocable<dump_range, T>) {; return dump_range{}(std::forward<T>(val)); } return "== dump error =="; } template<class T> void debug(T&& val, const std::string& endl) { *cdebug << dump(val) << endl << std::flush; } constexpr std::string WHITESPACES = " \n\r\t\f\v"; std::string ltrim(const std::string &s) { size_t start = s.find_first_not_of(WHITESPACES); return (start == std::string::npos) ? "" : s.substr(start); } std::string rtrim(const std::string &s) { size_t end = s.find_last_not_of(WHITESPACES); return (end == std::string::npos) ? "" : s.substr(0, end + 1); } std::string trim(const std::string &s) { return rtrim(ltrim(s)); } std::vector<std::string> split(const std::string& str) { static constexpr char SEPARATOR = ','; static constexpr char ESCAPE = '\\'; static constexpr char QUOTATIONS[] = "\"\'"; static constexpr char PARENTHESES[] = "()[]{}<>"; static constexpr auto PARENTHESES_KINDS = std::char_traits<char>::length(PARENTHESES); static_assert(PARENTHESES_KINDS % 2 == 0); std::vector<std::string> res = { "" }; bool quoted = false; std::array<int,(PARENTHESES_KINDS / 2)> enclosed = { 0 }; for(auto itr = std::ranges::begin(str); itr != std::ranges::end(str); ++itr) { if(std::ranges::find(QUOTATIONS, *itr) != std::ranges::end(QUOTATIONS)) { if(itr == std::ranges::begin(str) or *std::ranges::prev(itr) != ESCAPE) { quoted ^= true; } } if(const auto found = std::ranges::find(PARENTHESES, *itr); found != std::ranges::end(PARENTHESES)) { if(not quoted) { auto& target = enclosed[std::ranges::distance(std::begin(PARENTHESES), found) / 2]; target = std::max(0, target - static_cast<int>((std::ranges::distance(std::begin(PARENTHESES), found) % 2) * 2) + 1); } } if( not quoted and static_cast<std::size_t>(std::ranges::count(enclosed, 0)) == std::ranges::size(enclosed) and *itr == SEPARATOR ) { res.push_back(""); } else { res.back() += *itr; } } for(auto&& v : res) v = trim(v); return res; } template<class Arg> void raw(std::nullptr_t, Arg&& arg) { *cdebug << std::forward<Arg>(arg) << std::flush; } template<class Arg> void raw(Arg&& arg) { *cdebug << dump(std::forward<Arg>(arg)) << std::flush; } void debug(std::vector<std::string>, size_t, int) { debug(nullptr, COLOR_INIT + "\n"); } std::map<int, int> count; template<typename Head, typename... Tail> void debug(std::vector<std::string> args, size_t idx, int line, Head&& H, Tail&&... T) { if(idx == 0) { debug(nullptr, "\033[3;35m#" + std::to_string(line) + " (" + std::to_string(count[line]) + ")" + COLOR_INIT); count[line]++; } debug(nullptr, "\n - "); const std::string content = dump(H); const std::string type_name = get_type_name(std::forward<Head>(H)); debug(nullptr, "\033[32m" + args[idx] + COLOR_INIT + " : "); debug(nullptr, content); if(type_name.size() + content.size() >= 300) debug(nullptr, "\n "); debug(nullptr, " " + type_name); debug(args, idx + 1, 0, std::forward<Tail>(T)...); } }
/* [end]: debugger/debug.hpp*/
#ifdef LOCAL_JUDGE
#define DEBUGGER_ENABLED 1
#define debug(...) debugger::debug(debugger::split(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#define debug_(...) do { debugger::raw(nullptr, "\033[3;35m#" + std::to_string(__LINE__) + "\033[m "); debugger::raw(__VA_ARGS__); debugger::raw(nullptr, "\033[m\n"); } while(0);
#define DEBUG if constexpr(true)
#else
#define debug(...) ({ ; })
#define debug_(...) ({ ; })
#define DEBUG if constexpr(false)
#endif
/* [end]: template/debug.hpp*/

using mint = atcoder::modint998244353;


signed main() {
    int n, m, k; std::cin >> n >> m >> k;

    std::vector<std::vector<int>> to(n);
    for([[maybe_unused]] const int _ : std::views::iota(0, m)) {
        int u, v; std::cin >> u >> v, --u, --v;
        to[u].push_back(v);
        to[v].push_back(u);
    }

    std::vector<long> pow(n + 1);
    pow[0] = 1;
    for(const int i : std::views::iota(0, n)) pow[i + 1] = pow[i] * (k + 1);

    lib::leveler<long> level(std::vector<int>(n, k + 1));

    std::vector<std::vector<mint>> dp(level.sup() + 1);
    for(auto& v : dp) v.resize(n);

    for(const int i : std::views::iota(0, n)) dp[pow[i]][i] = 1;

    for(const int x : std::views::iota(0, level.sup())) {
        auto v = level.revert(x) | std::views::reverse;
        // debug(x, v);
        for(const int i : std::views::iota(0, n)) {
            if(v[i] == 0) continue;
            for(const int t : to[i]) {
                if(v[t] == k) continue;
                long nx = x + pow[t];
                // debug(t, level.revert(nx) | std::views::reverse);
                dp[nx][t] += dp[x][i];
            }
        }
    }

    mint ans = 0;

    for(const int i : std::views::iota(0, n)) {
        ans += dp[level.sup() - 1][i];
    }

    std::cout << ans.val() << "\n";
}