/*
 * @uni_kakurenbo
 * https://github.com/uni-kakurenbo/competitive-programming-workspace
 *
 * CC0 1.0  http://creativecommons.org/publicdomain/zero/1.0/deed.ja
 */
/* #language C++ GCC */
/* #region template */
#include <bits/stdc++.h>

/* #expanded [template.hpp] */
/* #expanded [snippet/aliases.hpp] */
#include <cstdint>
#include <utility>
/* #expanded [snippet/internal/types.hpp] */
#include <cstdint>
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;}
/* [snippet/internal/types.hpp] */
#define until(...) while(!(__VA_ARGS__))
#define ALL(x) std::begin((x)),std::end((x))
#define RALL(x) std::rbegin((x)),std::rend((x))
#define $F first
#define $S second
namespace lib {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) { return a = a | b; }bit_reference operator &= (bit_reference a, const bool b) { return a = a & b; }}
/* [snippet/aliases.hpp] */
/* #expanded [snippet/iterations.hpp] */
/* #expanded [snippet/internal/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
/* [snippet/internal/overload.hpp] */
#define LOOP(n) REPI($_, (n))
#define REPI(i,n) for(int i=0, i##_length=(n); i<i##_length; ++i)
#define REPF(i,l,r) for(auto i=(l), i##_last=(r); i<i##_last; ++i)
#define REPIS(i,l,r,s) for(auto 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(auto i=(r), i##_last=(l); --i>=i##_last;)
#define REPRS(i,l,r,s) for(auto i=(r), i##_last=(l); (i-=(s))>=i##_last;)
#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=(n); i<=i##_last; ++i)
#define FORI(i,l,r) for(auto i=(l), i##_last=(r); i<=i##_last; ++i)
#define FORIS(i,l,r,s) for(auto 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(auto i=(r), i##_last=(l); i>=i##_last; --i)
#define FORRS(i,l,r,s) for(auto i=(r), 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 ITR(...) $OVERLOAD5(__VA_ARGS__, ITR4, ITR3, ITR2, ITR1)(__VA_ARGS__)
#define ITRP(...) $OVERLOAD5(__VA_ARGS__, ITRP4, ITRP3, ITRP2, ITRP1)(__VA_ARGS__)
#define ITRR(...) $OVERLOAD5(__VA_ARGS__, ITRR4, ITRR3, ITRR2, ITRR1)(__VA_ARGS__)
/* [snippet/iterations.hpp] */
/* #expanded [snippet/fast_io.hpp] */
#include <iostream>
#ifdef __GNUC__
__attribute__((constructor)) inline void fast_io() { std::ios::sync_with_stdio(false), std::cin.tie(nullptr); }
#else
inline void fast_io() { std::ios::sync_with_stdio(false), std::cin.tie(nullptr); }
#endif
/* [snippet/fast_io.hpp] */
/* #expanded [snippet/using.hpp] */
#include <iostream>
#include <utility>
#include <tuple>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <bitset>
#include <queue>
#include <stack>
/* #expanded [utilities.hpp] */
/* #expanded [numeric/int128.hpp] */
#include <cctype>
#include <cassert>
#include <iostream>
#include <string>
#include <algorithm>
template<class C, class S>std::basic_istream<C,S>& operator>>(std::basic_istream<C,S>& in, lib::i128& v) {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>std::basic_ostream<C,S>& operator<<(std::basic_ostream<C,S>& out, lib::i128 v) {if(v == 0) return out << 0;if(v < 0) out << '-', v *= -1;std::string str;while(v > 0) str += v%10 + '0', v /= 10;std::reverse(str.begin(), str.end());return out << str;}
/* [numeric/int128.hpp] */
/* #expanded [geometry.hpp] */
/* #expanded [geometry/basic.hpp] */
/* #expanded [geometry/point.hpp] */
#include <complex>
#include <cmath>
#include <iostream>
#include <utility>
namespace lib {template <class T> struct point : protected std::pair<T,T> {public:constexpr point() {}constexpr point(const T& x, const T& y) : std::pair<T,T>(x, y) {}template<class U> constexpr point(const point<U>& p) : point(p.x(), p.y()) {};template<class U> constexpr point(point<U>&& p) : point(p.x(), p.y()) {};template<class U>constexpr point& operator=(const point<U>& p) & { this->x() = p.x(),this->y() = p.y(); return *this; };template<class U>constexpr point& operator=(point<U>&& p) && { this->x() = p.x(), this->y() = p.y(); return *this; };inline T& x() { return this->first; }inline T& y() { return this->second; }inline const T& x() const { return this->first; }inline const T& y() const { return this->second; }inline constexpr point& operator+=(const point& v) { this->x() += v.x(), this->y() += v.y(); return *this; }inline constexpr point& operator-=(const point& v) { this->x() -= v.x(), this->y() -= v.y(); return *this; }friend inline constexpr point operator+(point a, const point& b) { return a += b; }friend inline constexpr point operator-(point a, const point& b) { return a -= b; }friend inline constexpr point operator*(const point& a, const point& b) { return a.x() * b.x() + a.y() * b.y(); }friend inline constexpr bool operator==(const point& a, const point& b) { return a.x() == b.x() && a.y() == b.y(); }friend inline constexpr bool operator!=(const point& a, const point& b) { return a.x() != b.x() or a.y() != b.y(); }friend inline constexpr bool operator<(const point& a, const point& b) { return a.x() != b.x() ? a.x() < b.x() : a.y() < b.y(); }friend inline constexpr bool operator>(const point& a, const point& b) { return a.x() != b.x() ? a.x() > b.x() : a.y() > b.y(); }friend inline constexpr bool operator<=(const point& a, const point& b) { return !(a > b); }friend inline constexpr bool operator>=(const point& a, const point& b) { return !(a < b); }std::pair<T,T> _debug() const { return { this->x(), this->y() }; }};}template<class T>inline constexpr T std::abs(const lib::point<T>& v) {T x = v.x(), y = v.y(), n = std::max(std::abs(x), std::abs(y));if(n == 0) return 0;x /= n, y /= n;return n * std::sqrt(x * x + y * y);}namespace lib {template<class U, class T>inline constexpr U distance(const point<T>& a, const point<T>& b) {return std::abs(point<U>(a - b));}template<class T>inline constexpr T cross(point<T> a, point<T> b, const point<T>& o = {}) {a -= o, b -= o;return a.x() * b.y() - a.y() * b.x();}}template<class T, class C, class S>std::basic_istream<C,S>& operator>>(std::basic_istream<C,S>& in, lib::point<T>& v) {T x, y; in >> x >> y;v = { x, y };return in;}
/* [geometry/point.hpp] */
/* [geometry/basic.hpp] */
/* [geometry.hpp] */
/* #expanded [numeric/arithmetic.hpp] */
#include <cassert>
#include <cstring>
#include <string>
#include <algorithm>
#include <atcoder/math.hpp>
/* #expanded [internal/types.hpp] */
#include <cstdint>
namespace lib {namespace internal {using size_t = std::int32_t;using int128_t = __int128_t;using uint128_t = __uint128_t;}}
/* [internal/types.hpp] */
/* #expanded [numeric/internal/number_base.hpp] */
#include <cassert>
#include <cstddef>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
namespace lib {template<std::size_t B = 2, class T>std::string base_n_string(T v) {constexpr char CHARS[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";static_assert(0 < B <= std::strlen(CHARS));assert(0 <= v);std::string res;while(v > 0) {res += CHARS[v%B] + '0';v /= B;}std::reverse(ALL(res));return res;}template<class T>std::string base_n_string(T v, std::size_t b = 2) {constexpr char CHARS[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";assert(1 < b && b <= std::strlen(CHARS));assert(0 <= v);std::string res;while(v > 0) {res += CHARS[v%b];v /= b;}std::reverse(ALL(res));return res;}template<class T>std::vector<T> base_n_vector(T v, std::size_t b = 2) {assert(1 < b);assert(0 <= v);std::vector<T> res;while(v > 0) {res.push_back(v%b);v /= b;}std::reverse(ALL(res));return res;}}
/* [numeric/internal/number_base.hpp] */
namespace lib {template<class T>T nPr(const T n, T r) {assert(0 <= n);assert(0 <= r);if(n < r) return 0;T res = 1;REP(i, r) res *= n-i;return res;}template<class T>T nCr(const T n, T r) {assert(0 <= n);assert(0 <= r);if(n == r) return 1;if(n < r) return 0;if(n < r*2) r = n-r;T p = 1, q = 1;REP(i, r) p *= n-i, q *= r-i;return p / q;}template<class T, class U>T pow(T x, U n) {T res = 1;while(n > 0) {if(n & 1) res *= x;x *= x;n >>= 1;}return res;}using atcoder::pow_mod;using atcoder::inv_mod;using atcoder::crt;template<class T, class U, class V>inline bool mul_over(T x, U y, V s){if(x >= s) return true;if(x >= 0 && y >= 0) return x > s/y;if(x <= 0 && y <= 0) return x < s/y;return false;}template<class T, class U, class V>inline bool mul_under(T x, U y, V s){if(x <= s) return true;if(x >= 0 && y <= 0) return x > s/y;if(x <= 0 && y >= 0) return x < s/y;return false;}}
/* [numeric/arithmetic.hpp] */
/* #expanded [numeric/matrix.hpp] */
#include <cassert>
#include <vector>
/* #expanded [grid.hpp] */
#include <cassert>
#include <iostream>
#include <vector>
#include <string>
#include <type_traits>
#include <iterator>
#include <initializer_list>
#include <utility>
/* #expanded [internal/dev_env.hpp] */
#ifdef LOCAL_JUDGE
constexpr bool DEV_ENV = true;
#else
constexpr bool DEV_ENV = false;
#endif
/* [internal/dev_env.hpp] */
namespace lib {namespace internal {namespace grid_impl {template<class T>struct interface {virtual void assign(const size_t, const size_t, const T&&) = 0;virtual void resize(const size_t, const size_t) = 0;virtual size_t height() const = 0;virtual size_t width() const = 0;virtual size_t id(const size_t, const size_t) const = 0;virtual T& operator()(const size_t, const size_t) = 0;virtual const T& operator()(const size_t, const size_t) const = 0;};template<class T> struct container_base : virtual interface<T> {private:size_t _h, _w;protected:inline void _validate_index(__attribute__ ((unused)) const size_t i, __attribute__ ((unused)) const size_t j) const {assert(0 <= i and i < this->height());assert(0 <= j and j < this->width());}inline size_t _positivize_row_index(const size_t x) const {return x < 0 ? this->height() + x : x;}inline size_t _positivize_col_index(const size_t x) const {return x < 0 ? this->width() + x : x;}public:container_base() = default;container_base(const size_t _h, const size_t _w) : _h(_h), _w(_w) {}virtual void resize(const size_t h, const size_t w) override {this->_h = h, this->_w = w;}inline size_t height() const override { return this->_h; }inline size_t width() const override { return this->_w; }inline size_t id(const size_t i, const size_t j) const override {const size_t _i = this->_positivize_row_index(i);const size_t _j = this->_positivize_col_index(j);this->_validate_index(_i, _j);return _i * this->width() + _j;}};template<class T, class Row = std::vector<T>, class base = std::vector<Row>>struct container : base, container_base<T>, virtual interface<T> {container(const size_t n = 0) : container(n, n) {}container(const size_t h, const size_t w, const T &&val = T{}) : base(h, Row(w, std::forward<const T>(val))), container_base<T>(h, w) {}container(const std::initializer_list<Row> init_list) : base(init_list) {const size_t rows = std::distance(ALL(init_list));const size_t first_cols = init_list.begin()->size();if constexpr (DEV_ENV) { ITR(init_row, init_list) assert((size_t)init_row.size() == first_cols); }this->container_base<T>::resize(rows, first_cols);}inline void assign(const container &source) {this->resize(source.height(), source.width());this->base::assign(ALL(source));}inline void assign(const size_t h, const size_t w, const T &&val = T{}) override {this->container_base<T>::resize(h, w);this->base::resize(h);ITRR(row, *this) row.assign(w, std::forward<const T>(val));}inline void resize(const size_t h, const size_t w) override {this->container_base<T>::resize(h, w);this->base::resize(h);ITRR(row, *this) row.resize(w);}inline T& operator()(const size_t i, const size_t j) override {const size_t _i = this->_positivize_row_index(i);const size_t _j = this->_positivize_col_index(j);this->_validate_index(_i, _j);return (*this)[_i][_j];}inline const T& operator()(const size_t i, const size_t j) const override {const size_t _i = this->_positivize_row_index(i);const size_t _j = this->_positivize_col_index(j);this->_validate_index(_i, _j);return (*this)[_i][_j];}};template<class T, class base = std::vector<T>>struct unfolded_container : base, container_base<T>, virtual interface<T> {unfolded_container(size_t n = 0) : unfolded_container(n, n) {}unfolded_container(const size_t h, const size_t w, const T &&val = T{}) : base(h*w, std::forward<const T>(val)), container_base<T>(h, w) {}unfolded_container(std::initializer_list<std::initializer_list<T>> init_list) {const size_t rows = std::distance(init_list.begin(), init_list.end());const size_t first_cols = init_list.begin()->size();this->resize(rows, first_cols);for(auto index=0, itr=init_list.begin(), itr_end=init_list.end(); itr!=itr_end; ++itr) {assert((size_t)itr->size() == first_cols);for(auto v=itr->begin(), v_end=itr->end(); v!=v_end; ++v) (*this)[index++] = *v;}}inline void assign(const unfolded_container &source) {this->resize(source.height(), source.width());this->base::assign(ALL(source));}inline void assign(const size_t h, const size_t w, const T &&val = T{}) override {this->container_base<T>::resize(h, w);this->base::assign(h*w, std::forward<const T>(val));}inline void resize(const size_t h, const size_t w) override {this->container_base<T>::resize(h, w);this->base::resize(h*w);}inline T& operator()(const size_t i, const size_t j) override {const size_t _i = this->_positivize_row_index(i);const size_t _j = this->_positivize_col_index(j);return (*this)[this->id(_i, _j)];}inline const T& operator()(const size_t i, const size_t j) const override {const size_t _i = this->_positivize_row_index(i);const size_t _j = this->_positivize_col_index(j);return (*this)[this->id(_i, _j)];}};}template<class T, class container> struct grid_core : container, virtual grid_impl::interface<T> {using container::container;enum class invert_direction { vertical, horizontal };enum class rotate_direction { counter_clockwise, clockwise };template<class U = T, class Stream = std::istream>void inline read(Stream *const ist = &std::cin) {REP(i, this->height()) REP(j, this->width()) {U val; *ist >> val;(*this)(i, j) = val;}}template<invert_direction DIRECTION = invert_direction::vertical>inline grid_core& invert() {grid_core res(this->height(), this->width());REP(i, this->height()) REP(j, this->width()) {if constexpr (DIRECTION == invert_direction::vertical) {res(i,j) = (*this)(this->height()-i-1,j);}else {res(i,j) = (*this)(i, this->width()-j-1);}}this->assign(res);return *this;}template<rotate_direction DIRECTION = rotate_direction::clockwise>inline grid_core& rotate(const size_t k) {grid_core res = *this;REP(i, k) { res = res.rotate<DIRECTION>(); }this->assign(res);return *this;}template<rotate_direction DIRECTION = rotate_direction::clockwise>inline grid_core& rotate() {grid_core res(this->width(), this->height());REP(i, this->width()) REP(j, this->height()) {if constexpr (DIRECTION == rotate_direction::clockwise) {res(i,j) = (*this)(this->height()-j-1,i);}else {res(i,j) = (*this)(j,this->width()-i-1);}}this->assign(res);return *this;}inline grid_core& transpose() {grid_core res(this->width(), this->height());REP(i, this->width()) REP(j, this->height()) {res(i,j) = (*this)(j,i);}this->assign(res);return *this;}};}template<class T, class Row = std::vector<T>, class base = std::vector<Row>>using grid = internal::grid_core<T,internal::grid_impl::container<T,Row,base>>;template<class T, class base = std::vector<T>>using unfolded_grid = internal::grid_core<T,internal::grid_impl::unfolded_container<T,base>>;}
/* [grid.hpp] */
/* #expanded [valarray.hpp] */
#include <cassert>
#include <valarray>
#include <algorithm>
#include <type_traits>
#include <iterator>
#include <initializer_list>
namespace lib {template<class T> struct valarray : std::valarray<T> {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 {return 0 <= p and p < this->size();}inline bool _validate_index_in_closed([[maybe_unused]] const size_type p) const {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 {return 0 <= l and l <= r and r <= this->size();}inline size_type _positivize_index(const size_type p) const {return p < 0 ? this->size() + p : p;}public:valarray() {}valarray(const size_type length, const T& val = T{}) : std::valarray<T>(std::forward<const T>(val), length) {}template<class I, typename std::iterator_traits<I>::value_type* = nullptr>valarray(const I first, const I last) : std::valarray<T>(first, last) {}template<class U> valarray(const std::initializer_list<U>& init) : valarray(std::begin(init), std::end(init)) {}inline size_type size() const { return this->std::valarray<T>::size(); }inline void reserve(const size_type) {}template<class I, typename std::iterator_traits<I>::value_type* = nullptr>inline void assign(const I first, const I last) {this->resize(std::distance(first, last));std::copy(first, last, begin(*this));}inline void assign(const size_type length, const T& val = T{}) {this->std::valarray<T>::resize(length, val);}inline void resize(const size_type length, const T& val = T{}) {std::valarray<T> 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 {pos = this->_positivize_index(pos), assert(this->_validate_index_in_right_open(pos));return this->std::valarray<T>::operator[](pos);}inline T& operator[](size_type pos) {pos = this->_positivize_index(pos), assert(this->_validate_index_in_right_open(pos));return this->std::valarray<T>::operator[](pos);}inline const T& back() const { return *std::prev(this->end()); }inline T& back() { return *std::prev(this->end()); }inline const T& front() const { return *this->begin(); }inline T& front() { return *this->begin(); }inline const T* begin() const { return this->size() ? std::addressof((*this)[0]) : nullptr; }inline T* begin() { return this->size() ? std::addressof((*this)[0]) : nullptr; }inline const T* end() const { if(auto n = this->size()) { return std::addressof((*this)[0]) + n; } else { return nullptr; } }inline T* end() { if(auto n = this->size()) { return std::addressof((*this)[0]) + n; } else { return nullptr; } }};}
/* [valarray.hpp] */
namespace lib {namespace internal {namespace matrix_impl {template<class T> struct interface : virtual grid_impl::interface<T> {virtual size_t rows() const = 0;virtual size_t cols() const = 0;virtual size_t square() const = 0;};}template<class T, class base>struct matrix_core : base, virtual matrix_impl::interface<T> {using base::base;static inline matrix_core identity(const size_t n, const T &&val = { 1 }) {matrix_core res(n);REP(i, n) res(i, i) = val;return res;}inline size_t rows() const override { return this->height(); }inline size_t cols() const override { return this->width(); }inline size_t square() const override { return this->rows() == this->cols(); }template<class U> inline matrix_core& operator+=(const U rhs) {REP(i, this->rows()) REP(j, this->cols()) (*this)(i, j) += rhs;return *this;}template<class ...U> inline matrix_core& operator+=(const matrix_core<U...> rhs) {REP(i, this->rows()) REP(j, this->cols()) (*this)(i, j) += rhs(i, j);return *this;}template<class U> inline matrix_core operator+(const U rhs) const {return matrix_core(*this) += rhs;}template<class U> inline matrix_core& operator-=(const U rhs) {REP(i, this->rows()) REP(j, this->cols()) (*this)(i, j) -= rhs;return *this;}template<class ...U> inline matrix_core& operator-=(const matrix_core<U...> rhs) {REP(i, this->rows()) REP(j, this->cols()) (*this)(i, j) -= rhs(i, j);return *this;}template<class U> inline matrix_core operator-(const U rhs) const {return matrix_core(*this) -= rhs;}template<class ...U> inline matrix_core operator*(const matrix_core<U...> rhs) {assert(this->cols() == rhs.rows());matrix_core res(this->rows(), rhs.cols());REP(i, this->rows()) REP(j, rhs.cols()) REP(k, this->cols()) {res(i, j) += (*this)(i, k) * rhs(k, j);}return res;}template<class U> inline matrix_core operator*(const U rhs) {matrix_core res(*this);REP(i, res.rows()) REP(j, res.cols()) res(i, j) *= rhs;return res;}template<class U> inline matrix_core& operator*=(const U rhs) {matrix_core res = *this * rhs;this->assign(res);return *this;}template<class U> inline matrix_core& operator/=(const U rhs) {REP(i, this->rows()) REP(j, this->cols()) (*this)(i, j) /= rhs;return *this;}template<class U> inline matrix_core operator/(const U rhs) const {return matrix_core(*this) /= rhs;}template<class U> inline matrix_core& operator%=(const U rhs) {REP(i, this->rows()) REP(j, this->cols()) (*this)(i, j) %= rhs;return *this;}template<class U> inline matrix_core operator%(const U rhs) const {return matrix_core(*this) %= rhs;}inline matrix_core pow(ll p) {assert(this->square());matrix_core x = *this, res = matrix_core::Identity(this->rows());while(p > 0) {if(p & 1) res *= x;x *= x;p >>= 1;}return res;}};}template<class T, class base = grid<T>>using matrix = internal::matrix_core<T,base>;template<class T>using valmatrix = internal::matrix_core<T,unfolded_grid<T,valarray<T>>>;template<class T>using unfolded_matrix = internal::matrix_core<T,unfolded_grid<T>>;}
/* [numeric/matrix.hpp] */
/* #expanded [numeric/modint.hpp] */
#include <cassert>
#include <cstdint>
#include <atcoder/modint>
namespace lib {template <int _mod> using static_modint = atcoder::static_modint<_mod>;using modint998244353 = atcoder::modint998244353;using modint1000000007 = atcoder::modint1000000007;template <int id> using dynamic_modint = atcoder::dynamic_modint<id>;using modint = atcoder::modint;template<int> struct dynamic_modint_64bit;using modint64 = dynamic_modint_64bit<-1>;}namespace lib {template <int id> struct dynamic_modint_64bit : atcoder::internal::modint_base {private:using mint = dynamic_modint_64bit;using int64_t = std::int64_t;using uint64_t = std::uint64_t;using uint128_t = internal::uint128_t;protected:static uint64_t _mod;static uint64_t r;static uint64_t n2;static uint64_t get_r() {uint64_t res = _mod;for(int64_t i = 0; i < 5; ++i)res *= 2 - _mod * res;return res;}static uint64_t reduce(const uint128_t &b) {return (b + uint128_t(uint64_t(b) * uint64_t(-r)) * _mod) >> 64;}public:static uint64_t mod() { return _mod; }static void set_mod(const uint64_t m) {assert(m < (1UL << 63));assert((m & 1) == 1);_mod = m;n2 = -static_cast<uint128_t>(m) % m;r = get_r();assert(r * _mod == 1);}uint64_t _val;dynamic_modint_64bit() : _val(0) {}dynamic_modint_64bit(const std::int64_t b): _val(this->reduce((static_cast<uint128_t>(b) + this->_mod) * this->n2)) {};mint &operator+=(const mint &b) {if(static_cast<int64_t>(_val += b._val - 2 * _mod) < 0) this->_val += 2 * this->_mod;return *this;}mint &operator-=(const mint &b) {if(static_cast<int64_t>(this->_val -= b._val) < 0)this->_val += 2 * this->_mod;return *this;}mint &operator*=(const mint &b) {this->_val = reduce(static_cast<uint128_t>(this->_val) * b._val);return *this;}mint &operator/=(const mint &b) {*this *= b.inv();return *this;}mint operator+(const mint &b) const { return mint(*this) += b; }mint operator-(const mint &b) const { return mint(*this) -= b; }mint operator*(const mint &b) const { return mint(*this) *= b; }mint operator/(const mint &b) const { return mint(*this) /= b; }bool operator==(const mint &b) const {return (this->_val >= this->_mod ? this->_val - this->_mod : this->_val) == (b._val >= this->_mod ? b._val - this->_mod : b._val);}bool operator!=(const mint &b) const {return (this->_val >= this->_mod ? this->_val - this->_mod : this->_val) != (b._val >= this->_mod ? b._val - this->_mod : b._val);}mint operator-() const { return mint{} - static_cast<mint>(*this); }mint pow(uint128_t n) const {mint res(1), mul(*this);while(n > 0) {if(n & 1)res *= mul;mul *= mul;n >>= 1;}return res;}mint inv() const { return this->pow(this->_mod - 2); }uint64_t val() const {uint64_t res = this->reduce(this->_val);return res >= this->_mod ? res - this->_mod : res;}};template<int id> typename dynamic_modint_64bit<id>::uint64_t dynamic_modint_64bit<id>::_mod;template<int id> typename dynamic_modint_64bit<id>::uint64_t dynamic_modint_64bit<id>::r;template<int id> typename dynamic_modint_64bit<id>::uint64_t dynamic_modint_64bit<id>::n2;}
/* [numeric/modint.hpp] */
/* #expanded [constants.hpp] */
#include <cstdint>
#include <utility>
#include <limits>
namespace lib {i32 INF32 = (std::numeric_limits<i32>::max() >> 1) - 1;i64 INF64 = (std::numeric_limits<i64>::max() >> 1) - 1;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> DIRS8[] = { { -1, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 }, { 1, 0 }, { 1, -1 }, { 0, -1 }, { -1, -1 } };enum class comp : std::int8_t {equal_to,not_equal_to,equals = equal_to,eq = equal_to,under,over,or_under,or_over,less = under,more = over,less_than = under,more_than = over,not_less_than = or_over,not_more_than = or_under,leq = or_under,geq = or_over};enum class interval : std::int8_t {right_open,left_open,open,closed,};}
/* [constants.hpp] */
/* #expanded [multi_container.hpp] */
#include <cassert>
#include <vector>
#include <array>
/* #expanded [internal/exception.hpp] */
namespace lib {namespace internal {template<class... T> constexpr bool EXCEPTION = false;template<const int T> constexpr bool EXCEPTION_INT = false;}}
/* [internal/exception.hpp] */
namespace lib {namespace internal {namespace multi_container_impl {template<class container> struct base : container {using container::container;protected:inline void _validate_index(__attribute__ ((unused)) const internal::size_t index) const {assert(0 <= index and index < (internal::size_t)this->size());}inline internal::size_t _positivize_index(const internal::size_t x) const {return x < 0 ? this->size() + x : x;}};}}template<class T, const unsigned int RANK, template<class...> class container = valarray>struct multi_container : internal::multi_container_impl::base<container<multi_container<T,RANK-1,container>>> {using internal::multi_container_impl::base<container<multi_container<T,RANK-1,container>>>::base;template<class Head, class... Tail>multi_container(const Head head, const Tail... tail): internal::multi_container_impl::base<container<multi_container<T,RANK-1,container>>>(head, multi_container<T,RANK-1,container>(tail...)) {static_assert(std::is_integral_v<Head>, "size must be integral");}template<class Head, class... Tail> T& operator()(const Head _head, const Tail... tail) {static_assert(std::is_integral_v<Head>, "index must be integral");const internal::size_t head = this->_positivize_index(_head);this->_validate_index(head);return (*this)[head](tail...);}template<class Head, class... Tail> const T& operator()(const Head _head, const Tail... tail) const {static_assert(std::is_integral_v<Head>, "index must be integral");const internal::size_t head = this->_positivize_index(_head);this->_validate_index(head);return (*this)[head](tail...);}};template<class T, template<class...> class container>struct multi_container<T,1,container> : internal::multi_container_impl::base<container<T>> {using internal::multi_container_impl::base<container<T>>::base;template<class... Args> multi_container(const Args&... args) : internal::multi_container_impl::base<container<T>>(args...) {}T& operator()(const internal::size_t _index) {const internal::size_t index = this->_positivize_index(_index);this->_validate_index(index);return (*this)[index];}const T& operator()(const internal::size_t _index) const {const internal::size_t index = this->_positivize_index(_index);this->_validate_index(index);return (*this)[index];}};template<class T, template<class...> class container>struct multi_container<T,0,container> {static_assert(internal::EXCEPTION<T>, "invalid rank: 0, should be 1 or more");};}
/* [multi_container.hpp] */
/* #expanded [graph.hpp] */
#include <cassert>
#include <tuple>
#include <vector>
#include <iostream>
/* #expanded [data_structure/disjoint_set_union.hpp] */
#include <cassert>
#include <algorithm>
#include <cassert>
#include <vector>
namespace lib {struct dsu {using size_type = internal::size_t;private:size_type _n, _group_count;mutable std::vector<size_type> _parent_or_size;public:dsu() : _n(0) {}explicit dsu(const size_type n) : _n(n), _group_count(n), _parent_or_size(n, -1) {}inline size_type size() const { return this->_n; }inline size_type group_count() const { return this->_group_count; }inline size_type merge(const size_type a, const size_type b) {assert(0 <= a && a < _n);assert(0 <= b && b < _n);size_type x = this->leader(a), y = this->leader(b);if (x == y) return x;--this->_group_count;if (-this->_parent_or_size[x] < -this->_parent_or_size[y]) std::swap(x, y);this->_parent_or_size[x] += this->_parent_or_size[y];this->_parent_or_size[y] = x;return x;}inline bool same(const size_type a, const size_type b) const {assert(0 <= a && a < _n);assert(0 <= b && b < _n);return this->leader(a) == this->leader(b);}inline size_type leader(const size_type a) const {assert(0 <= a && a < _n);if (_parent_or_size[a] < 0) return a;return _parent_or_size[a] = this->leader(_parent_or_size[a]);}inline size_type size(const size_type a) const {assert(0 <= a && a < _n);return -_parent_or_size[this->leader(a)];}inline std::vector<std::vector<size_type>> groups() const {std::vector<size_type> leader_buf(_n), group_size(_n);for (size_type i = 0; i < _n; i++) {leader_buf[i] = this->leader(i);group_size[leader_buf[i]]++;}std::vector<std::vector<size_type>> result(_n);for (size_type i = 0; i < _n; i++) {result[i].reserve(group_size[i]);}for (size_type i = 0; i < _n; i++) {result[leader_buf[i]].push_back(i);}result.erase(std::remove_if(result.begin(), result.end(),[&](const std::vector<size_type>& v) { return v.empty(); }),result.end());return result;}};}
/* [data_structure/disjoint_set_union.hpp] */
namespace lib {namespace internal {namespace graph_impl {template<class cost_t, class size_type> struct edge {private:inline static internal::size_t unique() { static internal::size_t id = 0; return id++; }public:using cost_type = cost_t;const internal::size_t id = unique();const size_type from, to; const cost_t cost;edge(const size_type u, const size_type v, const cost_t w) : from(u), to(v), cost(w) {}std::tuple<size_type,size_type,cost_t> _debug() const { return { from, to, cost }; };friend bool operator==(const edge& lhs, const edge& rhs) { return lhs.id == rhs.id; }friend bool operator!=(const edge& lhs, const edge& rhs) { return lhs.id != rhs.id; }};}}template<class C = ll>struct graph : std::vector<std::vector<internal::graph_impl::edge<C,internal::size_t>>> {using size_type = internal::size_t;using cost_type = C;using edge = typename internal::graph_impl::edge<cost_type,size_type>;enum class edge_type { undirected, directed };private:size_type _directed_edge_count, _undirected_edge_count;protected:inline void _add_edge(const size_type u, const size_type v, const cost_type w) {this->operator[](u).emplace_back(u, v, w);++this->_directed_edge_count;}public:explicit graph(const size_type n = 0) : std::vector<std::vector<edge>>(n) {}inline void clear() { ITR(row, *this) row.clear(); }inline size_type vertexes() const { return this->size(); }inline size_type edges() const { return this->inputted.size(); }template<const edge_type EDGE_TYPE = edge_type::directed>inline void add_edge(const size_type u, const size_type v, const cost_type w = 1) {assert(0 <= u and u < this->vertexes()), assert(0 <= v and v < this->vertexes());this->_add_edge(u, v, w);if constexpr(EDGE_TYPE == edge_type::undirected) this->_add_edge(v, u, w);++this->_undirected_edge_count;}inline void add_edge_bidirectionally(const size_type u, const size_type v, const cost_type w = 1) {this->add_edge<edge_type::undirected>(u, v, w);}template<bool WEIGHTED = false, bool ONE_ORIGIN = true, const edge_type EDGE_TYPE = edge_type::directed, class Stream = std::istream>void inline read(const size_type edges, Stream *const ist = &std::cin) {REP(edges) {size_type u, v; cost_type w = 1; *ist >> u >> v; if(ONE_ORIGIN) --u, --v;if(WEIGHTED) *ist >> w;this->add_edge<EDGE_TYPE>(u, v, w);}}template<bool WEIGHTED = false, bool ONE_ORIGIN = true, class Stream = std::istream>void inline read_bidirectionally(const size_type edges, Stream *const ist = &std::cin) {REP(edges) {size_type u, v; cost_type w = 1; *ist >> u >> v; if(ONE_ORIGIN) --u, --v;if(WEIGHTED) *ist >> w;this->add_edge<edge_type::undirected>(u, v, w);}}template<class cost_t = cost_type> inline void distances_without_cost(const size_type, std::vector<cost_t> *const) const;template<class cost_t = cost_type> inline std::vector<cost_t> distances_without_cost(const size_type) const;template<class cost_t = cost_type> inline void distances_with_01cost(const size_type, std::vector<cost_t> *const) const;template<class cost_t = cost_type> inline std::vector<cost_t> distances_with_01cost(const size_type) const;template<class cost_t = cost_type> inline void distances(const size_type, std::vector<cost_t> *const) const;template<class cost_t = cost_type> inline std::vector<cost_t> distances(const size_type) const;inline bool sort_topologically(std::vector<size_type> *const ) const;inline bool sort_topologically() const;template<class> inline bool sort_topologically_with_priority(std::vector<size_type> *const) const;template<class> inline bool sort_topologically_with_priority() const;inline size_type minimum_paph_cover_size_as_dag() const;template<class cost_t = cost_type>inline cost_t minimum_spanning_tree_cost() const;template<class cost_t = cost_type>inline cost_t maximum_spanning_tree_cost() const;inline dsu components() const;template<class G, class U = char>inline void from_grid(const G&, U = '.');template<class I, class J = I, class distance_type = cost_type, class = internal::size_t>inline distance_type build_manhattan_mst(const I, const I, const J, const J);};}
/* [graph.hpp] */
/* #expanded [string.hpp] */
#include <string>
#include <iterator>
namespace lib {template<class I, class Res = std::string>Res to_lower(const I first, const I last) {Res res;res.reserve(std::distance(first, last));std::transform(first, last, std::back_inserter(res), ::tolower);return res;}template<class I, class Res = std::string>Res to_uppwer(const I first, const I last) {Res res;res.reserve(std::distance(first, last));std::transform(first, last, std::back_inserter(res), ::toupper);return res;}template<class Res = std::string>Res to_lower(const std::string str) {return to_lower<std::string::const_iterator,Res>(std::begin(str), std::end(str));}template<class Res = std::string>Res to_uppwer(const std::string str) {return to_uppwer<std::string::const_iterator,Res>(std::begin(str), std::end(str));}}
/* [string.hpp] */
/* #expanded [adapter/set.hpp] */
#include <set>
#include <unordered_set>
#include <iterator>
#include <optional>
/* #expanded [utility/functional.hpp] */
#include <functional>
#include <utility>
namespace lib {namespace internal {template<class T> constexpr T plus(const T a, const T b) { return std::plus<T>{}(a, b); }template<class T> constexpr T minus(const T a, const T b) { return std::minus<T>{}(a, b); }template<class T> constexpr T bitxor(const T a, const T b) { return a xor b; }}template<class T1, class T2> inline auto mod(T1 x, T2 r) { return (x%r+r)%r; }template<class T1, class T2> inline bool chmax(T1 &a, T2 b) { return (a<b ? a=b, true : false); }template<class T1, class T2> inline bool chmin(T1 &a, T2 b) { return (a>b ? a=b, true : false); }template<class T> inline constexpr T sign(const T x) {return (x > 0) - (x < 0);}template<class T, T FROM_MIN, T FROM_MAX, T TO_MIN, T TO_MAX> inline constexpr T mapping(const T x) {return (x - FROM_MIN) * (TO_MAX - TO_MIN) / (FROM_MAX - FROM_MIN) + TO_MIN;}template<class T> inline constexpr T mapping(const T x, const T from_min, const T from_max, const T to_min, const T to_max) {return (x - from_min) * (to_max - to_min) / (from_max - from_min) + to_min;}}
/* [utility/functional.hpp] */
namespace lib {namespace internal {template<class set> struct set_wrapper : set {using set::set;using size_type = internal::size_t;inline size_type size() const { return this->set::size(); }inline bool contains(const typename set::key_type& key) { return static_cast<bool>(this->count(key)); }inline auto remove(const typename set::key_type& key) { return this->erase(this->find(key)); }inline auto min_element() { return this->begin(); }inline auto max_element() { return this->begin(); }inline auto min() { return *this->begin(); }inline auto max() { return *this->end(); }inline void pop_min() { return this->erase(this->begin()); }inline void pop_max() { return this->erase(this->end()); }inline auto next_element(const typename set::key_type& key, const size_type _count = 0) {size_type count = std::abs(_count);auto itr = this->lower_bound(key);const auto begin = this->begin(), end = this->end();if(itr == end) return this->end();if(itr == begin) return this->begin();while(count--) {if(_count < 0) if(itr-- == begin) return this->begin();if(_count > 0) if(++itr == end) return this->end();}return itr;}inline auto prev_element(const typename set::key_type& key, const size_type _count = 0) {size_type count = std::abs(_count);auto itr = this->upper_bound(key);const auto begin = this->begin(), end = this->end();if(itr == end) return this->end();if(itr-- == begin) return this->begin();while(count--) {if(_count < 0) if(itr-- == begin) return this->begin();if(_count > 0) if(++itr == end) return this->end();}return itr;}inline std::optional<typename set::value_type> next(const typename set::key_type& key, size_type count = 0) {auto itr = this->lower_bound(key);const auto end = this->end();if(itr == end) return {};while(count--) if(++itr == end) return {};return { *itr };}inline std::optional<typename set::value_type> prev(const typename set::key_type& key, size_type count = 0) {auto itr = this->upper_bound(key);const auto begin = this->begin();if(itr-- == begin) return {};while(count--) if(itr-- == begin) return {};return { *itr };}};}template<class... Args> using set = internal::set_wrapper<std::set<Args...>>;template<class... Args> using unordered_set = internal::set_wrapper<std::unordered_set<Args...>>;template<class... Args> using multiset = internal::set_wrapper<std::multiset<Args...>>;template<class... Args> using unordered_multiset = internal::set_wrapper<std::unordered_multiset<Args...>>;}
/* [adapter/set.hpp] */
/* #expanded [utility/applier.hpp] */
#include <utility>
#include <algorithm>
namespace lib {namespace internal {template<class T> T max(T a, T b) { return std::max(a, b); }template<class T> T max(T x) { return x; }template<class T> T max() { return -std::numeric_limits<T>::min(); }template<class T> T min(T a, T b) { return std::min(a, b); }template<class T> T min(T x) { return x; }template<class T> T min() { return std::numeric_limits<T>::max(); }}template<class T, T (*op)(T,T)> struct applier {using value_type = T;protected:T _v;public:applier(const T& v = T{}) : _v(v) {}template<class U> applier& operator<<=(U&& val) & noexcept {_v = op(_v, std::forward<U>(val));return *this;}inline T val() const { return _v; }inline operator T() const { return _v; }};template<class T> using maximum = applier<T,internal::max<T>>;template<class T> using minimum = applier<T,internal::min<T>>;}
/* [utility/applier.hpp] */
/* #expanded [utility/restrictor.hpp] */
#include <utility>
namespace lib {template<class T, T INF, T SUP> struct static_restrictor {using restrictor = static_restrictor;protected:T _v;inline void _clamp() { this->_v = std::clamp(this->_v, INF, SUP); }inline restrictor& _assign(T v) {this->_v = std::clamp(v, INF, SUP);return *this;}public:static_restrictor(T v = T{}) : _v(v) {}inline T val() const { return this->_v; }restrictor& operator++() { return this->_assign(this->_v + 1); }restrictor& operator--() { return this->_assign(this->_v - 1); }restrictor operator++(int) {restrictor res = *this;*this++;return res;}restrictor operator--(int) {restrictor res = *this;*this--;return res;}restrictor& operator+=(const restrictor& rhs) { return this->_assign(this->_v + rhs.val()); }restrictor& operator-=(const restrictor& rhs) { return this->_assign(this->_v - rhs.val()); }restrictor& operator*=(const restrictor& rhs) {if(mul_over(this->_v, rhs.val(), SUP)) return this->_assign(SUP);if(mul_under(this->_v, rhs.val(), INF)) return this->_assign(INF);return this->_assign(this->_v * rhs.val());}restrictor& operator/=(const restrictor& rhs) { return this->_assign(this->_v / rhs.val()); }restrictor operator+() const { return *this; }restrictor operator-() const { return restrictor() - *this; }friend restrictor operator+(const restrictor& lhs, const restrictor& rhs) {return restrictor(lhs) += rhs;}friend restrictor operator-(const restrictor& lhs, const restrictor& rhs) {return restrictor(lhs) -= rhs;}friend restrictor operator*(const restrictor& lhs, const restrictor& rhs) {return restrictor(lhs) *= rhs;}friend restrictor operator/(const restrictor& lhs, const restrictor& rhs) {return restrictor(lhs) /= rhs;}friend bool operator==(const restrictor& lhs, const restrictor& rhs) {return lhs._v == rhs._v;}friend bool operator!=(const restrictor& lhs, const restrictor& rhs) {return lhs._v != rhs._v;}friend bool operator<(const restrictor& lhs, const restrictor& rhs) {return lhs._v < rhs._v;}friend bool operator>(const restrictor& lhs, const restrictor& rhs) {return lhs._v > rhs._v;}friend bool operator<=(const restrictor& lhs, const restrictor& rhs) {return lhs._v <= rhs._v;}friend bool operator>=(const restrictor& lhs, const restrictor& rhs) {return lhs._v >= rhs._v;}};}namespace std {template<class T, T INF, T SUP>T std::abs(const lib::static_restrictor<T,INF,SUP>& v) { return std::abs(v.val()); }}
/* [utility/restrictor.hpp] */
/* #expanded [iterable/applied.hpp] */
#include <algorithm>
#include <vector>
#include <iterator>
namespace lib {template<class I, class F, class C = std::vector<typename std::iterator_traits<I>::value_type>>inline auto applied(const I first, const I last, F&& func) {C res(first, last);func(std::begin(res), std::end(res));return res;}template<class V, class F, class C = V>inline auto applied(V v, F&& func) {return applied<typename V::iterator,F,C>(std::begin(v), std::end(v), func);}template<class I>inline auto sorted(const I first, const I last) {return applied(first, last, std::sort<I>);}template<class V>inline auto sorted(V v) {return applied(v, std::sort<typename V::iterator>);}template<class I>inline auto reversed(const I first, const I last) {return applied(first, last, std::reverse<I>);}template<class V>inline auto reversed(V v) {return applied(v, std::reverse<typename V::iterator>);}}
/* [iterable/applied.hpp] */
/* #expanded [iterable/accumulation.hpp] */
#include <cassert>
#include <iterator>
#include <vector>
#include <functional>
#include <numeric>
namespace lib {template<class T = i64, class container = valarray<T>>struct accumulation : container {using size_type = internal::size_t;protected:inline size_type _positivize_index(const size_type x) const {return x < 0 ? std::size(*this) + x : x;}public:accumulation() {}template<class I, class Operator = std::plus<T>>accumulation(const I first, const I last, const T head = T{}, const Operator op = std::plus<T>{}) {this->assign(std::distance(first, last) + 1, {});std::exclusive_scan(first, last, std::begin(*this), head, op);if(this->size() > 1) *std::prev(this->end()) = op(*std::prev(std::end(*this), 2), *std::prev(last));}template<class Operaotr = std::minus<T>>inline T operator()(size_type left, size_type right, Operaotr op = std::minus<T>{}) const {left = _positivize_index(left), right = _positivize_index(right);assert(0 <= left and left <= right and right < (size_type)std::size(*this));return op((*this)[right], (*this)[left]);}};template<class T, class container = valarray<valarray<T>>, class Operator = std::plus<T>>struct accumulation_2d : container {using size_type = internal::size_t;protected:inline size_type _positivize_index(const size_type x) const {return x < 0 ? std::size(*this) + x : x;}Operator _op;public:accumulation_2d() {}template<class I>accumulation_2d(const I first, const I last, const T head = T{}, const Operator op = std::plus<T>{}) : _op(op) {const size_type h = std::distance(first, last);const size_type w = std::distance(std::begin(*first), std::end(*first));{auto row = first;this->assign(h+1, head);(*this)[0].assign(w+1, head);REP(i, h) {assert(w == std::distance(std::begin(*row), std::end(*row)));(*this)[i+1].assign(w+1, head);REP(j, w) (*this)[i+1][j+1] = first[i][j];++row;}}FOR(i, 1, h) FOR(j, w) (*this)[i][j] = op((*this)[i][j], (*this)[i-1][j]);FOR(i, h) FOR(j, 1, w) (*this)[i][j] = op((*this)[i][j], (*this)[i][j-1]);}template<class Rev = std::minus<T>>inline T operator()(size_type a, size_type b, size_type c, size_type d, const Rev rev = std::minus<T>{}) const {a = _positivize_index(a), b = _positivize_index(b);c = _positivize_index(c), d = _positivize_index(d);assert(0 <= a and a <= b and b < (size_type)std::size(*this));assert(0 <= c and c <= d and d < (size_type)std::size((*this)[0]));return this->_op(rev((*this)[b][d], this->_op((*this)[a][d], (*this)[b][c])), (*this)[a][c]);}template<class Rev = std::minus<T>>inline T operator()(const std::pair<size_type,size_type> p, const std::pair<size_type,size_type> q, const Rev rev = std::minus<T>{}) const {return this->operator()(p.first, p.second, q.first, q.second, rev);}};}
/* [iterable/accumulation.hpp] */
/* #expanded [iterable/operation.hpp] */
#include <string>
#include <iterator>
#include <numeric>
namespace lib {template<class I>std::string join(const I first, const I last, const std::string& sep = "") {std::ostringstream res;std::copy(first, last, std::ostream_iterator<typename std::iterator_traits<I>::value_type>(res, sep));return res.str();}template<class V>std::string join(V& v, const std::string& sep = "") {return join(std::begin(v), std::end(v), sep);}template<class I, class T = typename std::iterator_traits<I>::value_type>T sum(const I first, const I second, const T& base = 0) {return std::accumulate(first, second, base);}template<class V, class T = typename V::value_type>auto sum(V& v, T base = 0) {return sum(std::begin(v), std::end(v), base);}}
/* [iterable/operation.hpp] */
/* #expanded [iterable/mex.hpp] */
#include <iterator>
#include <algorithm>
namespace lib {template<class I, class T = typename std::iterator_traits<I>::value_type>T mex(const I first, const I last, const T& base = 0) {std::vector<T> val(first, last);std::sort(val.begin(), val.end());val.erase(std::unique(val.begin(), val.end()), val.end());val.erase(val.begin(), std::lower_bound(val.begin(), val.end(), base));internal::size_t i = 0;while(i < (internal::size_t)val.size() and val[i] == T{i} + base) ++i;return T{i} + base;}template<class V, class T = typename V::value_type>auto mex(const V v, const T& base = 0) {return mex(v.begin(), v.end(), base);}}
/* [iterable/mex.hpp] */
/* [utilities.hpp] */
using std::cin;using std::cout;using std::pair;using std::tuple;using std::vector;using std::array;using std::string;using std::queue;using std::stack;using std::priority_queue;using std::bitset;using std::sort;using std::reverse;using std::map;using std::unordered_map;using std::min_element;using std::max_element;using lib::i32;using lib::u32;using lib::i64;using lib::u64;
#ifdef __GNUC__
using lib::i128;using lib::u128;
#endif
using lib::uint;using lib::ll;using lib::ull;using lib::ld;using lib::INF32;using lib::INF64;using lib::LN;using lib::SPC;using lib::DIRS4;using lib::DIRS8;using lib::nPr;using lib::nCr;using lib::pow;using lib::pow_mod;using lib::inv_mod;using lib::spair;using lib::valarray;using lib::multi_container;using lib::minimum;using lib::maximum;using lib::modint998244353;using lib::modint1000000007;using lib::modint;using lib::modint64;using lib::sorted;using lib::reversed;using lib::join;using lib::chmin;using lib::chmax;using lib::grid;using lib::graph;using lib::matrix;using lib::unordered_multiset;using lib::set;using lib::unordered_set;using lib::multiset;using lib::unordered_multiset;
/* [snippet/using.hpp] */
#ifdef LOCAL_JUDGE
#include<debug>
#define debug(...) debugger::debug(debugger::split(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#define DEBUG(...) do { debugger::DEBUG(nullptr, "\033[3;35m#" + std::to_string(__LINE__) + "\033[m "); debugger::DEBUG(__VA_ARGS__); debugger::DEBUG(nullptr, "\033[m\n"); } while(0);
#else
#define debug(...) ({ ; })
#define DEBUG(...) ({ ; })
#endif
/* #expanded [adapter/input.hpp] */
#include <atcoder/modint>
#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <utility>
/* #expanded [internal/resolving_rank.hpp] */
namespace lib {namespace internal {template<int P> struct resolving_rank : resolving_rank<P-1> {};template<> struct resolving_rank<0> {};}}
/* [internal/resolving_rank.hpp] */
template<class source = std::istream>struct input_adapter {private:template<class T>auto _set(lib::internal::resolving_rank<3>, T *const val) -> decltype(std::declval<source&>() >> *val, 0) {*this->in >> *val;return 0;}template<class T>auto _set(lib::internal::resolving_rank<2>, T *const val) -> decltype(std::begin(*val), std::end(*val), 0) {(*this)(std::begin(*val), std::end(*val));return 0;}template<class T>auto _set(lib::internal::resolving_rank<1>, T *const val) -> decltype(val->first, val->second, 0) {(*this)(&*val);return 0;}template<class T>auto _set(lib::internal::resolving_rank<0>, T *const val) -> std::enable_if_t<atcoder::internal::is_modint<T>::value,int> {long long v; std::cin >> v;*val = { v };return 0;}protected:template<class T>source *set(T *const val) {this->_set(lib::internal::resolving_rank<3>{}, val);return this->in;}public:using char_type = typename source::char_type;source *in;input_adapter(source *in = &std::cin) : in(in) {}template<class T> inline input_adapter& operator>>(T &s) {this->set(&s);return *this;}template<class T> inline T one() {T val; *this >> val;return val;}template<class T> inline void operator()(T*const val) {*this >> *val;}template<class T, class... Args> inline void operator()(T *const head, Args *const... tail) {*this >> *head;(*this)(tail...);}template<class I, class = typename std::iterator_traits<I>::value_type> inline void operator()(I first, I last) {for(I itr=first; itr!=last; ++itr) *this >> *itr;}template<class F, class S> inline void operator()(std::pair<F,S> *const p) {*this >> p->first >> p->second;}};
/* [adapter/input.hpp] */
/* #expanded [adapter/output.hpp] */
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <iterator>
template<class destination = std::ostream, class Terminator = std::string, class Separator = std::string>struct output_adapter {private:template<class T>auto _put(lib::internal::resolving_rank<2>, const T &val) -> decltype(std::declval<destination&>() << val, 0) {*this->out << val;return 0;}template<class T>auto _put(lib::internal::resolving_rank<1>, const T &val) -> decltype(val.val(), 0) {this->put(val.val());return 0;}template<class T>auto _put(lib::internal::resolving_rank<0>, const T &val) -> decltype(std::begin(val), std::end(val), 0) {(*this)(std::begin(val), std::end(val), false);return 0;}protected:template<class T>destination *put(const T &val) {this->_put(lib::internal::resolving_rank<2>{}, val);return this->out;}public:using char_type = typename destination::char_type;static constexpr auto sendl = std::endl<char_type,std::char_traits<char_type>>;destination *out;Terminator endline;Separator separator;output_adapter(destination *out = &std::cout, Terminator endline = "\n", Separator separator = " "): out(out), endline(endline), separator(separator){*this << std::fixed << std::setprecision(20);}inline void seekp(const typename destination::off_type off, const std::ios_base::seekdir dir = std::ios_base::cur) { this->out->seekp(off, dir); };template<class T> inline output_adapter& operator<<(const T &s) {this->put(s);return *this;}template<class T = std::string> inline void operator()(const T &val = "") {*this << val << this->endline;}template<class T, class ...Args> inline void operator()(const T &head, const Args& ...tail) {*this << head << this->separator;(*this)(tail...);}template<class I, class = typename std::iterator_traits<I>::iterator_category> inline void operator()(const I first, const I last, const bool terminate = true) {for(I itr=first; itr!=last;) {*this << *itr;if(++itr == last) {if(terminate) *this << this->endline;}else *this << this->separator;}}template<class T> inline void operator()(const std::initializer_list<T> vals) {std::vector wrapped(vals.begin(), vals.end());(*this)(wrapped.begin(), wrapped.end());}template<class F, class S> inline void operator()(const std::pair<F,S> &p) {(*this)(p.first, p.second);}};
/* [adapter/output.hpp] */
input_adapter _input;output_adapter _print;
#define input _input
#define print _print
/* [template.hpp] */
/* #endregion */

void solve();

signed main() {
    int $ = 1;
    // std::cin >> $;
    for(int _ = 0; _ < $; ++_) {
        DEBUG("Case: #" + std::to_string(_));
        solve();
    }
    return 0;
}

/* #expanded [iterable/counter.hpp] */
#include <iterator>
#include <unordered_map>
namespace lib {template<class T = i64, class container = std::unordered_map<T,internal::size_t>>struct counter : container {counter() {}template<class I> counter(const I first, const I last) {for(auto itr=first; itr!=last; ++itr) ++(*this)[*itr];}};}
/* [iterable/counter.hpp] */

void solve() {
    i64 n, p; cin >> n >> p;
    valarray<i64> a(n); input >> a;

    debug(a);

    i64 ans = 0;

    for(int k=1; lib::pow(p, k) <= INF32; ++k) {
        valarray<i64> b = a; b %= lib::pow(p, k);
        lib::counter<int> cnt(ALL(b));
        debug(cnt);
        ITR(v, cnt) ans += lib::nCr<i64>(v.second, 2);
        debug(ans);
    }

    print(ans);
}