#include using namespace std; using pint = pair; using pll = pair; template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } // 4-neighbor (or 8-neighbor) const vector dx = {1, 0, -1, 0, 1, -1, 1, -1}; const vector dy = {0, 1, 0, -1, 1, 1, -1, -1}; /*///////////////////////////////////////////////////////*/ // debug /*///////////////////////////////////////////////////////*/ #define DEBUG 1 #define COUT(x) if (DEBUG) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl template ostream& operator << (ostream &s, pair P) { return s << '<' << P.first << ", " << P.second << '>'; } template ostream& operator << (ostream &s, vector P) { for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; } template ostream& operator << (ostream &s, deque P) { for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; } template ostream& operator << (ostream &s, vector > P) { for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; } template ostream& operator << (ostream &s, set P) { for (auto it : P) { s << "<" << it << "> "; } return s; } template ostream& operator << (ostream &s, multiset P) { for (auto it : P) { s << "<" << it << "> "; } return s; } template ostream& operator << (ostream &s, map P) { for (auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s; } /*///////////////////////////////////////////////////////*/ // QCFium 法 /*///////////////////////////////////////////////////////*/ #pragma GCC target("avx2") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") /*/////////////////////////////*/ // modint, FPS /*/////////////////////////////*/ // modint template struct Fp { // inner value long long val; // constructor constexpr Fp() : val(0) { } constexpr Fp(long long v) : val(v % MOD) { if (val < 0) val += MOD; } constexpr long long get() const { return val; } constexpr int get_mod() const { return MOD; } // arithmetic operators constexpr Fp operator + () const { return Fp(*this); } constexpr Fp operator - () const { return Fp(0) - Fp(*this); } constexpr Fp operator + (const Fp &r) const { return Fp(*this) += r; } constexpr Fp operator - (const Fp &r) const { return Fp(*this) -= r; } constexpr Fp operator * (const Fp &r) const { return Fp(*this) *= r; } constexpr Fp operator / (const Fp &r) const { return Fp(*this) /= r; } constexpr Fp& operator += (const Fp &r) { val += r.val; if (val >= MOD) val -= MOD; return *this; } constexpr Fp& operator -= (const Fp &r) { val -= r.val; if (val < 0) val += MOD; return *this; } constexpr Fp& operator *= (const Fp &r) { val = val * r.val % MOD; return *this; } constexpr Fp& operator /= (const Fp &r) { long long a = r.val, b = MOD, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b, swap(a, b); u -= t * v, swap(u, v); } val = val * u % MOD; if (val < 0) val += MOD; return *this; } constexpr Fp pow(long long n) const { Fp res(1), mul(*this); while (n > 0) { if (n & 1) res *= mul; mul *= mul; n >>= 1; } return res; } constexpr Fp inv() const { Fp res(1), div(*this); return res / div; } // other operators constexpr bool operator == (const Fp &r) const { return this->val == r.val; } constexpr bool operator != (const Fp &r) const { return this->val != r.val; } constexpr Fp& operator ++ () { ++val; if (val >= MOD) val -= MOD; return *this; } constexpr Fp& operator -- () { if (val == 0) val += MOD; --val; return *this; } constexpr Fp operator ++ (int) const { Fp res = *this; ++*this; return res; } constexpr Fp operator -- (int) const { Fp res = *this; --*this; return res; } friend constexpr istream& operator >> (istream &is, Fp &x) { is >> x.val; x.val %= MOD; if (x.val < 0) x.val += MOD; return is; } friend constexpr ostream& operator << (ostream &os, const Fp &x) { return os << x.val; } friend constexpr Fp pow(const Fp &r, long long n) { return r.pow(n); } friend constexpr Fp inv(const Fp &r) { return r.inv(); } }; // Binomial coefficient template struct BiCoef { vector fact_, inv_, finv_; constexpr BiCoef() {} constexpr BiCoef(int n) : fact_(n, 1), inv_(n, 1), finv_(n, 1) { init(n); } constexpr void init(int n) { fact_.assign(n, 1), inv_.assign(n, 1), finv_.assign(n, 1); int MOD = fact_[0].get_mod(); for(int i = 2; i < n; i++){ fact_[i] = fact_[i-1] * i; inv_[i] = -inv_[MOD%i] * (MOD/i); finv_[i] = finv_[i-1] * inv_[i]; } } constexpr mint com(int n, int k) const { if (n < k || n < 0 || k < 0) return 0; return fact_[n] * finv_[k] * finv_[n-k]; } constexpr mint fact(int n) const { if (n < 0) return 0; return fact_[n]; } constexpr mint inv(int n) const { if (n < 0) return 0; return inv_[n]; } constexpr mint finv(int n) const { if (n < 0) return 0; return finv_[n]; } }; namespace NTT { long long modpow(long long a, long long n, int mod) { long long res = 1; while (n > 0) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res; } long long modinv(long long a, int mod) { long long b = mod, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b, swap(a, b); u -= t * v, swap(u, v); } u %= mod; if (u < 0) u += mod; return u; } int calc_primitive_root(int mod) { if (mod == 2) return 1; if (mod == 167772161) return 3; if (mod == 469762049) return 3; if (mod == 754974721) return 11; if (mod == 998244353) return 3; int divs[20] = {}; divs[0] = 2; int cnt = 1; long long x = (mod - 1) / 2; while (x % 2 == 0) x /= 2; for (long long i = 3; i * i <= x; i += 2) { if (x % i == 0) { divs[cnt++] = i; while (x % i == 0) x /= i; } } if (x > 1) divs[cnt++] = x; for (int g = 2;; g++) { bool ok = true; for (int i = 0; i < cnt; i++) { if (modpow(g, (mod - 1) / divs[i], mod) == 1) { ok = false; break; } } if (ok) return g; } } int get_fft_size(int N, int M) { int size_a = 1, size_b = 1; while (size_a < N) size_a <<= 1; while (size_b < M) size_b <<= 1; return max(size_a, size_b) << 1; } // number-theoretic transform template void trans(vector &v, bool inv = false) { if (v.empty()) return; int N = (int)v.size(); int MOD = v[0].get_mod(); int PR = calc_primitive_root(MOD); static bool first = true; static vector vbw(30), vibw(30); if (first) { first = false; for (int k = 0; k < 30; ++k) { vbw[k] = modpow(PR, (MOD - 1) >> (k + 1), MOD); vibw[k] = modinv(vbw[k], MOD); } } for (int i = 0, j = 1; j < N - 1; j++) { for (int k = N >> 1; k > (i ^= k); k >>= 1); if (i > j) swap(v[i], v[j]); } for (int k = 0, t = 2; t <= N; ++k, t <<= 1) { long long bw = vbw[k]; if (inv) bw = vibw[k]; for (int i = 0; i < N; i += t) { mint w = 1; for (int j = 0; j < t/2; ++j) { int j1 = i + j, j2 = i + j + t/2; mint c1 = v[j1], c2 = v[j2] * w; v[j1] = c1 + c2; v[j2] = c1 - c2; w *= bw; } } } if (inv) { long long invN = modinv(N, MOD); for (int i = 0; i < N; ++i) v[i] = v[i] * invN; } } // for garner static constexpr int MOD0 = 754974721; static constexpr int MOD1 = 167772161; static constexpr int MOD2 = 469762049; using mint0 = Fp; using mint1 = Fp; using mint2 = Fp; static const mint1 imod0 = 95869806; // modinv(MOD0, MOD1); static const mint2 imod1 = 104391568; // modinv(MOD1, MOD2); static const mint2 imod01 = 187290749; // imod1 / MOD0; // small case (T = mint, long long) template vector naive_mul(const vector &A, const vector &B) { if (A.empty() || B.empty()) return {}; int N = (int)A.size(), M = (int)B.size(); vector res(N + M - 1); for (int i = 0; i < N; ++i) for (int j = 0; j < M; ++j) res[i + j] += A[i] * B[j]; return res; } // mul by convolution template vector mul(const vector &A, const vector &B) { if (A.empty() || B.empty()) return {}; int N = (int)A.size(), M = (int)B.size(); if (min(N, M) < 30) return naive_mul(A, B); int MOD = A[0].get_mod(); int size_fft = get_fft_size(N, M); if (MOD == 998244353) { vector a(size_fft), b(size_fft), c(size_fft); for (int i = 0; i < N; ++i) a[i] = A[i]; for (int i = 0; i < M; ++i) b[i] = B[i]; trans(a), trans(b); vector res(size_fft); for (int i = 0; i < size_fft; ++i) res[i] = a[i] * b[i]; trans(res, true); res.resize(N + M - 1); return res; } vector a0(size_fft, 0), b0(size_fft, 0), c0(size_fft, 0); vector a1(size_fft, 0), b1(size_fft, 0), c1(size_fft, 0); vector a2(size_fft, 0), b2(size_fft, 0), c2(size_fft, 0); for (int i = 0; i < N; ++i) a0[i] = A[i].val, a1[i] = A[i].val, a2[i] = A[i].val; for (int i = 0; i < M; ++i) b0[i] = B[i].val, b1[i] = B[i].val, b2[i] = B[i].val; trans(a0), trans(a1), trans(a2), trans(b0), trans(b1), trans(b2); for (int i = 0; i < size_fft; ++i) { c0[i] = a0[i] * b0[i]; c1[i] = a1[i] * b1[i]; c2[i] = a2[i] * b2[i]; } trans(c0, true), trans(c1, true), trans(c2, true); mint mod0 = MOD0, mod01 = mod0 * MOD1; vector res(N + M - 1); for (int i = 0; i < N + M - 1; ++i) { int y0 = c0[i].val; int y1 = (imod0 * (c1[i] - y0)).val; int y2 = (imod01 * (c2[i] - y0) - imod1 * y1).val; res[i] = mod01 * y2 + mod0 * y1 + y0; } return res; } }; // Formal Power Series template struct FPS : vector { using vector::vector; // constructor constexpr FPS(const vector &r) : vector(r) {} // core operator constexpr FPS pre(int siz) const { return FPS(begin(*this), begin(*this) + min((int)this->size(), siz)); } constexpr FPS rev() const { FPS res = *this; reverse(begin(res), end(res)); return res; } constexpr FPS& normalize() { while (!this->empty() && this->back() == 0) this->pop_back(); return *this; } // basic operator constexpr FPS operator - () const noexcept { FPS res = (*this); for (int i = 0; i < (int)res.size(); ++i) res[i] = -res[i]; return res; } constexpr FPS operator + (const mint &v) const { return FPS(*this) += v; } constexpr FPS operator + (const FPS &r) const { return FPS(*this) += r; } constexpr FPS operator - (const mint &v) const { return FPS(*this) -= v; } constexpr FPS operator - (const FPS &r) const { return FPS(*this) -= r; } constexpr FPS operator * (const mint &v) const { return FPS(*this) *= v; } constexpr FPS operator * (const FPS &r) const { return FPS(*this) *= r; } constexpr FPS operator / (const mint &v) const { return FPS(*this) /= v; } constexpr FPS operator / (const FPS &r) const { return FPS(*this) /= r; } constexpr FPS operator % (const FPS &r) const { return FPS(*this) %= r; } constexpr FPS operator << (int x) const { return FPS(*this) <<= x; } constexpr FPS operator >> (int x) const { return FPS(*this) >>= x; } constexpr FPS& operator += (const mint &v) { if (this->empty()) this->resize(1); (*this)[0] += v; return *this; } constexpr FPS& operator += (const FPS &r) { if (r.size() > this->size()) this->resize(r.size()); for (int i = 0; i < (int)r.size(); ++i) (*this)[i] += r[i]; return this->normalize(); } constexpr FPS& operator -= (const mint &v) { if (this->empty()) this->resize(1); (*this)[0] -= v; return *this; } constexpr FPS& operator -= (const FPS &r) { if (r.size() > this->size()) this->resize(r.size()); for (int i = 0; i < (int)r.size(); ++i) (*this)[i] -= r[i]; return this->normalize(); } constexpr FPS& operator *= (const mint &v) { for (int i = 0; i < (int)this->size(); ++i) (*this)[i] *= v; return *this; } constexpr FPS& operator *= (const FPS &r) { return *this = NTT::mul((*this), r); } constexpr FPS& operator /= (const mint &v) { assert(v != 0); mint iv = modinv(v); for (int i = 0; i < (int)this->size(); ++i) (*this)[i] *= iv; return *this; } // division, r must be normalized (r.back() must not be 0) constexpr FPS& operator /= (const FPS &r) { assert(!r.empty()); assert(r.back() != 0); this->normalize(); if (this->size() < r.size()) { this->clear(); return *this; } int need = (int)this->size() - (int)r.size() + 1; *this = (rev().pre(need) * r.rev().inv(need)).pre(need).rev(); return *this; } constexpr FPS& operator %= (const FPS &r) { assert(!r.empty()); assert(r.back() != 0); this->normalize(); FPS q = (*this) / r; return *this -= q * r; } constexpr FPS& operator <<= (int x) { FPS res(x, 0); res.insert(res.end(), begin(*this), end(*this)); return *this = res; } constexpr FPS& operator >>= (int x) { FPS res; res.insert(res.end(), begin(*this) + x, end(*this)); return *this = res; } constexpr mint eval(const mint &v) { mint res = 0; for (int i = (int)this->size()-1; i >= 0; --i) { res *= v; res += (*this)[i]; } return res; } // advanced operation // df/dx constexpr FPS diff() const { int n = (int)this->size(); FPS res(n-1); for (int i = 1; i < n; ++i) res[i-1] = (*this)[i] * i; return res; } // \int f dx constexpr FPS integral() const { int n = (int)this->size(); FPS res(n+1, 0); for (int i = 0; i < n; ++i) res[i+1] = (*this)[i] / (i+1); return res; } // inv(f), f[0] must not be 0 constexpr FPS inv(int deg) const { assert((*this)[0] != 0); if (deg < 0) deg = (int)this->size(); FPS res({mint(1) / (*this)[0]}); for (int i = 1; i < deg; i <<= 1) { res = (res + res - res * res * pre(i << 1)).pre(i << 1); } res.resize(deg); return res; } constexpr FPS inv() const { return inv((int)this->size()); } // log(f) = \int f'/f dx, f[0] must be 1 constexpr FPS log(int deg) const { assert((*this)[0] == 1); FPS res = (diff() * inv(deg)).integral(); res.resize(deg); return res; } constexpr FPS log() const { return log((int)this->size()); } // exp(f), f[0] must be 0 constexpr FPS exp(int deg) const { assert((*this)[0] == 0); FPS res(1, 1); for (int i = 1; i < deg; i <<= 1) { res = res * (pre(i << 1) - res.log(i << 1) + 1).pre(i << 1); } res.resize(deg); return res; } constexpr FPS exp() const { return exp((int)this->size()); } // pow(f) = exp(e * log f) constexpr FPS pow(long long e, int deg) const { if (e == 0) { FPS res(deg, 0); res[0] = 1; return res; } long long i = 0; while (i < (int)this->size() && (*this)[i] == 0) ++i; if (i == (int)this->size() || i > (deg - 1) / e) return FPS(deg, 0); mint k = (*this)[i]; FPS res = ((((*this) >> i) / k).log(deg) * e).exp(deg) * mint(k).pow(e) << (e * i); res.resize(deg); return res; } constexpr FPS pow(long long e) const { return pow(e, (int)this->size()); } // sqrt(f), f[0] must be 1 constexpr FPS sqrt_base(int deg) const { assert((*this)[0] == 1); mint inv2 = mint(1) / 2; FPS res(1, 1); for (int i = 1; i < deg; i <<= 1) { res = (res + pre(i << 1) * res.inv(i << 1)).pre(i << 1); for (mint &x : res) x *= inv2; } res.resize(deg); return res; } constexpr FPS sqrt_base() const { return sqrt_base((int)this->size()); } // friend operators friend constexpr FPS diff(const FPS &f) { return f.diff(); } friend constexpr FPS integral(const FPS &f) { return f.integral(); } friend constexpr FPS inv(const FPS &f, int deg) { return f.inv(deg); } friend constexpr FPS inv(const FPS &f) { return f.inv((int)f.size()); } friend constexpr FPS log(const FPS &f, int deg) { return f.log(deg); } friend constexpr FPS log(const FPS &f) { return f.log((int)f.size()); } friend constexpr FPS exp(const FPS &f, int deg) { return f.exp(deg); } friend constexpr FPS exp(const FPS &f) { return f.exp((int)f.size()); } friend constexpr FPS pow(const FPS &f, long long e, int deg) { return f.pow(e, deg); } friend constexpr FPS pow(const FPS &f, long long e) { return f.pow(e, (int)f.size()); } friend constexpr FPS sqrt_base(const FPS &f, int deg) { return f.sqrt_base(deg); } friend constexpr FPS sqrt_base(const FPS &f) { return f.sqrt_base((int)f.size()); } }; /*/////////////////////////////*/ // Union-Find /*/////////////////////////////*/ // Union-Find struct UnionFind { // core member vector par, nex; // constructor UnionFind() { } UnionFind(int N) : par(N, -1), nex(N) { init(N); } void init(int N) { par.assign(N, -1); nex.resize(N); for (int i = 0; i < N; ++i) nex[i] = i; } // core methods int root(int x) { if (par[x] < 0) return x; else return par[x] = root(par[x]); } bool same(int x, int y) { return root(x) == root(y); } bool merge(int x, int y) { x = root(x), y = root(y); if (x == y) return false; if (par[x] > par[y]) swap(x, y); // merge technique par[x] += par[y]; par[y] = x; swap(nex[x], nex[y]); return true; } int size(int x) { return -par[root(x)]; } // get group vector group(int x) { vector res({x}); while (nex[res.back()] != x) res.push_back(nex[res.back()]); return res; } vector> groups() { vector> member(par.size()); for (int v = 0; v < (int)par.size(); ++v) { member[root(v)].push_back(v); } vector> res; for (int v = 0; v < (int)par.size(); ++v) { if (!member[v].empty()) res.push_back(member[v]); } return res; } // debug friend ostream& operator << (ostream &s, UnionFind uf) { const vector> &gs = uf.groups(); for (const vector &g : gs) { s << "group: "; for (int v : g) s << v << " "; s << endl; } return s; } }; /*/////////////////////////////*/ // Segment Tree /*/////////////////////////////*/ // Segment Tree template struct SegmentTree { using Func = function; // core member int N; Func OP; Monoid IDENTITY; // inner data int log, offset; vector dat; // constructor SegmentTree() {} SegmentTree(int n, const Func &op, const Monoid &identity) { init(n, op, identity); } SegmentTree(const vector &v, const Func &op, const Monoid &identity) { init(v, op, identity); } void init(int n, const Func &op, const Monoid &identity) { N = n; OP = op; IDENTITY = identity; log = 0, offset = 1; while (offset < N) ++log, offset <<= 1; dat.assign(offset * 2, IDENTITY); } void init(const vector &v, const Func &op, const Monoid &identity) { init((int)v.size(), op, identity); build(v); } void pull(int k) { dat[k] = OP(dat[k * 2], dat[k * 2 + 1]); } void build(const vector &v) { assert(N == (int)v.size()); for (int i = 0; i < N; ++i) dat[i + offset] = v[i]; for (int k = offset - 1; k > 0; --k) pull(k); } int size() const { return N; } Monoid operator [] (int i) const { return dat[i + offset]; } // update A[i], i is 0-indexed, O(log N) void set(int i, const Monoid &v) { assert(0 <= i && i < N); int k = i + offset; dat[k] = v; while (k >>= 1) pull(k); } // get [l, r), l and r are 0-indexed, O(log N) Monoid prod(int l, int r) { assert(0 <= l && l <= r && r <= N); Monoid val_left = IDENTITY, val_right = IDENTITY; l += offset, r += offset; for (; l < r; l >>= 1, r >>= 1) { if (l & 1) val_left = OP(val_left, dat[l++]); if (r & 1) val_right = OP(dat[--r], val_right); } return OP(val_left, val_right); } Monoid all_prod() { return dat[1]; } // get max r that f(get(l, r)) = True (0-indexed), O(log N) // f(IDENTITY) need to be True int max_right(const function f, int l = 0) { if (l == N) return N; l += offset; Monoid sum = IDENTITY; do { while (l % 2 == 0) l >>= 1; if (!f(OP(sum, dat[l]))) { while (l < offset) { l = l * 2; if (f(OP(sum, dat[l]))) { sum = OP(sum, dat[l]); ++l; } } return l - offset; } sum = OP(sum, dat[l]); ++l; } while ((l & -l) != l); // stop if l = 2^e return N; } // get min l that f(get(l, r)) = True (0-indexed), O(log N) // f(IDENTITY) need to be True int min_left(const function f, int r = -1) { if (r == 0) return 0; if (r == -1) r = N; r += offset; Monoid sum = IDENTITY; do { --r; while (r > 1 && (r % 2)) r >>= 1; if (!f(OP(dat[r], sum))) { while (r < offset) { r = r * 2 + 1; if (f(OP(dat[r], sum))) { sum = OP(dat[r], sum); --r; } } return r + 1 - offset; } sum = OP(dat[r], sum); } while ((r & -r) != r); return 0; } // debug friend ostream& operator << (ostream &s, const SegmentTree &seg) { for (int i = 0; i < (int)seg.size(); ++i) { s << seg[i]; if (i != (int)seg.size() - 1) s << " "; } return s; } }; // Lazy Segment Tree template struct LazySegmentTree { // various function types using FuncMonoid = function; using FuncAction = function; using FuncComposition = function; // core member int N; FuncMonoid OP; FuncAction ACT; FuncComposition COMP; Monoid IDENTITY_MONOID; Action IDENTITY_ACTION; // inner data int log, offset; vector dat; vector lazy; // constructor LazySegmentTree() {} LazySegmentTree(int n, const FuncMonoid op, const FuncAction act, const FuncComposition comp, const Monoid &identity_monoid, const Action &identity_action) { init(n, op, act, comp, identity_monoid, identity_action); } LazySegmentTree(const vector &v, const FuncMonoid op, const FuncAction act, const FuncComposition comp, const Monoid &identity_monoid, const Action &identity_action) { init(v, op, act, comp, identity_monoid, identity_action); } void init(int n, const FuncMonoid op, const FuncAction act, const FuncComposition comp, const Monoid &identity_monoid, const Action &identity_action) { N = n, OP = op, ACT = act, COMP = comp; IDENTITY_MONOID = identity_monoid, IDENTITY_ACTION = identity_action; log = 0, offset = 1; while (offset < N) ++log, offset <<= 1; dat.assign(offset * 2, IDENTITY_MONOID); lazy.assign(offset * 2, IDENTITY_ACTION); } void init(const vector &v, const FuncMonoid op, const FuncAction act, const FuncComposition comp, const Monoid &identity_monoid, const Action &identity_action) { init((int)v.size(), op, act, comp, identity_monoid, identity_action); build(v); } void build(const vector &v) { assert(N == (int)v.size()); for (int i = 0; i < N; ++i) dat[i + offset] = v[i]; for (int k = offset - 1; k > 0; --k) pull_dat(k); } int size() const { return N; } // basic functions for lazy segment tree void pull_dat(int k) { dat[k] = OP(dat[k * 2], dat[k * 2 + 1]); } void apply_lazy(int k, const Action &f) { dat[k] = ACT(f, dat[k]); if (k < offset) lazy[k] = COMP(f, lazy[k]); } void push_lazy(int k) { apply_lazy(k * 2, lazy[k]); apply_lazy(k * 2 + 1, lazy[k]); lazy[k] = IDENTITY_ACTION; } void pull_dat_deep(int k) { for (int h = 1; h <= log; ++h) pull_dat(k >> h); } void push_lazy_deep(int k) { for (int h = log; h >= 1; --h) push_lazy(k >> h); } // setter and getter, update A[i], i is 0-indexed, O(log N) void set(int i, const Monoid &v) { assert(0 <= i && i < N); int k = i + offset; push_lazy_deep(k); dat[k] = v; pull_dat_deep(k); } Monoid get(int i) { assert(0 <= i && i < N); int k = i + offset; push_lazy_deep(k); return dat[k]; } Monoid operator [] (int i) { return get(i); } // apply f for index i void apply(int i, const Action &f) { assert(0 <= i && i < N); int k = i + offset; push_lazy_deep(k); dat[k] = ACT(f, dat[k]); pull_dat_deep(k); } // apply f for interval [l, r) void apply(int l, int r, const Action &f) { assert(0 <= l && l <= r && r <= N); if (l == r) return; l += offset, r += offset; for (int h = log; h >= 1; --h) { if (((l >> h) << h) != l) push_lazy(l >> h); if (((r >> h) << h) != r) push_lazy((r - 1) >> h); } int original_l = l, original_r = r; for (; l < r; l >>= 1, r >>= 1) { if (l & 1) apply_lazy(l++, f); if (r & 1) apply_lazy(--r, f); } l = original_l, r = original_r; for (int h = 1; h <= log; ++h) { if (((l >> h) << h) != l) pull_dat(l >> h); if (((r >> h) << h) != r) pull_dat((r - 1) >> h); } } // get prod of interval [l, r) Monoid prod(int l, int r) { assert(0 <= l && l <= r && r <= N); if (l == r) return IDENTITY_MONOID; l += offset, r += offset; for (int h = log; h >= 1; --h) { if (((l >> h) << h) != l) push_lazy(l >> h); if (((r >> h) << h) != r) push_lazy(r >> h); } Monoid val_left = IDENTITY_MONOID, val_right = IDENTITY_MONOID; for (; l < r; l >>= 1, r >>= 1) { if (l & 1) val_left = OP(val_left, dat[l++]); if (r & 1) val_right = OP(dat[--r], val_right); } return OP(val_left, val_right); } Monoid all_prod() { return dat[1]; } // get max r that f(get(l, r)) = True (0-indexed), O(log N) // f(IDENTITY) need to be True int max_right(const function f, int l = 0) { if (l == N) return N; l += offset; push_lazy_deep(l); Monoid sum = IDENTITY_MONOID; do { while (l % 2 == 0) l >>= 1; if (!f(OP(sum, dat[l]))) { while (l < offset) { push_lazy(l); l = l * 2; if (f(OP(sum, dat[l]))) { sum = OP(sum, dat[l]); ++l; } } return l - offset; } sum = OP(sum, dat[l]); ++l; } while ((l & -l) != l); // stop if l = 2^e return N; } // get min l that f(get(l, r)) = True (0-indexed), O(log N) // f(IDENTITY) need to be True int min_left(const function f, int r = -1) { if (r == 0) return 0; if (r == -1) r = N; r += offset; push_lazy_deep(r - 1); Monoid sum = IDENTITY_MONOID; do { --r; while (r > 1 && (r % 2)) r >>= 1; if (!f(OP(dat[r], sum))) { while (r < offset) { push_lazy(r); r = r * 2 + 1; if (f(OP(dat[r], sum))) { sum = OP(dat[r], sum); --r; } } return r + 1 - offset; } sum = OP(dat[r], sum); } while ((r & -r) != r); return 0; } // debug stream friend ostream& operator << (ostream &s, LazySegmentTree seg) { for (int i = 0; i < (int)seg.size(); ++i) { s << seg[i]; if (i != (int)seg.size() - 1) s << " "; } return s; } // dump void dump() { for (int i = 0; i <= log; ++i) { for (int j = (1 << i); j < (1 << (i + 1)); ++j) { cout << "{" << dat[j] << "," << lazy[j] << "} "; } cout << endl; } } }; /*/////////////////////////////*/ // Solver /*/////////////////////////////*/ // dynamic modint struct DynamicModint { using mint = DynamicModint; // static menber static int MOD; // inner value long long val; // constructor DynamicModint() : val(0) { } DynamicModint(long long v) : val(v % MOD) { if (val < 0) val += MOD; } long long get() const { return val; } static int get_mod() { return MOD; } static void set_mod(int mod) { MOD = mod; } // arithmetic operators mint operator + () const { return mint(*this); } mint operator - () const { return mint(0) - mint(*this); } mint operator + (const mint &r) const { return mint(*this) += r; } mint operator - (const mint &r) const { return mint(*this) -= r; } mint operator * (const mint &r) const { return mint(*this) *= r; } mint operator / (const mint &r) const { return mint(*this) /= r; } mint& operator += (const mint &r) { val += r.val; if (val >= MOD) val -= MOD; return *this; } mint& operator -= (const mint &r) { val -= r.val; if (val < 0) val += MOD; return *this; } mint& operator *= (const mint &r) { val = val * r.val % MOD; return *this; } mint& operator /= (const mint &r) { long long a = r.val, b = MOD, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b, swap(a, b); u -= t * v, swap(u, v); } val = val * u % MOD; if (val < 0) val += MOD; return *this; } mint pow(long long n) const { mint res(1), mul(*this); while (n > 0) { if (n & 1) res *= mul; mul *= mul; n >>= 1; } return res; } mint inv() const { mint res(1), div(*this); return res / div; } // other operators bool operator == (const mint &r) const { return this->val == r.val; } bool operator != (const mint &r) const { return this->val != r.val; } mint& operator ++ () { ++val; if (val >= MOD) val -= MOD; return *this; } mint& operator -- () { if (val == 0) val += MOD; --val; return *this; } mint operator ++ (int) { mint res = *this; ++*this; return res; } mint operator -- (int) { mint res = *this; --*this; return res; } friend istream& operator >> (istream &is, mint &x) { is >> x.val; x.val %= x.get_mod(); if (x.val < 0) x.val += x.get_mod(); return is; } friend ostream& operator << (ostream &os, const mint &x) { return os << x.val; } friend mint pow(const mint &r, long long n) { return r.pow(n); } friend mint inv(const mint &r) { return r.inv(); } }; int DynamicModint::MOD; const int MOD = 998244353; using mint = Fp; int main() { int N, M, K; cin >> N >> M >> K; mint res = 0; vector dp(M+1, vector(1<= K) { dp[i+1][bit2] += dp[i][bit1]; } } } } for (int bit = 0; bit < (1<