//注意点 //Tは3つの値を持つ構造 //だがワイルドカードとしても使っている //#pragma GCC optimize ("-O3") #include using namespace std; //@起動時 struct initon { initon() { cin.tie(0); ios::sync_with_stdio(false); cout.setf(ios::fixed); cout.precision(16); srand((unsigned) clock() + (unsigned) time(NULL)); }; } __initon; //衝突対策 #define ws ___ws //@必須構造 struct T { int f, s, t; T() { f = -1, s = -1, t = -1; } T(int f, int s, int t) : f(f), s(s), t(t) {} bool operator<(const T &r) const { return f != r.f ? f < r.f : s != r.s ? s < r.s : t < r.t; //return f != r.f ? f > r.f : s != r.s ? s > r.s : t > r.t; 大きい順 } bool operator>(const T &r) const { return f != r.f ? f > r.f : s != r.s ? s > r.s : t > r.t; //return f != r.f ? f > r.f : s != r.s ? s > r.s : t > r.t; 小さい順 } bool operator==(const T &r) const { return f == r.f && s == r.s && t == r.t; } bool operator!=(const T &r) const { return f != r.f || s != r.s || t != r.t; } int operator[](int i) { assert(i < 3); return i == 0 ? f : i == 1 ? s : t; } }; struct F { int a, b, c, d; F() { a = -1, b = -1, c = -1, d = -1; } F(int a, int b, int c, int d) : a(a), b(b), c(c), d(d) {} bool operator<(const F &r) const { return a != r.a ? a < r.a : b != r.b ? b < r.b : c != r.c ? c < r.c : d < r.d; // return a != r.a ? a > r.a : b != r.b ? b > r.b : c != r.c ? c > r.c : d > r.d; } bool operator>(const F &r) const { return a != r.a ? a > r.a : b != r.b ? b > r.b : c != r.c ? c > r.c : d > r.d; // return a != r.a ? a < r.a : b != r.b ? b < r.b : c != r.c ? c < r.c : d < r.d; } bool operator==(const F &r) const { return a == r.a && b == r.b && c == r.c && d == r.d; } bool operator!=(const F &r) const { return a != r.a || b != r.b || c != r.c || d != r.d; } int operator[](int i) { assert(i < 4); return i == 0 ? a : i == 1 ? b : i == 2 ? c : d; } }; T mt(int a, int b, int c) { return T(a, b, c); } //@マクロ省略系 型,構造 #define int long long #define ll long long #define double long double #define ull unsigned long long using dou = double; using itn = int; using str = string; using bo= bool; using P = pair; #define fi first #define se second #define vec vector #define beg begin #define rbeg rbegin #define con continue #define bre break #define brk break #define is == //マクロ省略系 コンテナ using vi = vector; #define _overloadvvi(_1, _2, _3, _4, name, ...) name #define vvi1(a) vec a #define vvi2(a, b) vec a(b) #define vvi3(a, b, c) vec a(b,vi(c)) #define vvi4(a, b, c, d) vec a(b,vi(c,d)) #define vvi(...) _overloadvvi(__VA_ARGS__,vvi4,vvi3,vvi2 ,vvi1)(__VA_ARGS__) using vl = vector; #define _overloadvvl(_1, _2, _3, _4, name, ...) name #define vvl1(a) vec a #define vvl2(a, b) vec a(b) #define vvl3(a, b, c) vec a(b,vl(c)) #define vvl4(a, b, c, d) vec a(b,vl(c,d)) #define vvl(...) _overloadvvl(__VA_ARGS__,vvl4,vvl3,vvl2 ,vvl1)(__VA_ARGS__) using vb = vector; #define _overloadvvb(_1, _2, _3, _4, name, ...) name #define vvb1(a) vec a #define vvb2(a, b) vec a(b) #define vvb3(a, b, c) vec a(b,vb(c)) #define vvb4(a, b, c, d) vec a(b,vb(c,d)) #define vvb(...) _overloadvvb(__VA_ARGS__,vvb4,vvb3,vvb2 ,vvb1)(__VA_ARGS__) using vs = vector; #define _overloadvvs(_1, _2, _3, _4, name, ...) name #define vvs1(a) vec a #define vvs2(a, b) vec a(b) #define vvs3(a, b, c) vec a(b,vs(c)) #define vvs4(a, b, c, d) vec a(b,vs(c,d)) #define vvs(...) _overloadvvs(__VA_ARGS__,vvs4,vvs3,vvs2 ,vvs1)(__VA_ARGS__) using vd = vector; #define _overloadvvd(_1, _2, _3, _4, name, ...) name #define vvd1(a) vec a #define vvd2(a, b) vec a(b) #define vvd3(a, b, c) vec a(b,vd(c)) #define vvd4(a, b, c, d) vec a(b,vd(c,d)) #define vvd(...) _overloadvvd(__VA_ARGS__,vvd4,vvd3,vvd2 ,vvd1)(__VA_ARGS__) using vc=vector; #define _overloadvvc(_1, _2, _3, _4, name, ...) name #define vvc1(a) vec a #define vvc2(a, b) vec a(b) #define vvc3(a, b, c) vec a(b,vc(c)) #define vvc4(a, b, c, d) vec a(b,vc(c,d)) #define vvc(...) _overloadvvc(__VA_ARGS__,vvc4,vvc3,vvc2 ,vvc1)(__VA_ARGS__) using vp = vector

; #define _overloadvvp(_1, _2, _3, _4, name, ...) name #define vvp1(a) vec a #define vvp2(a, b) vec a(b) #define vvp3(a, b, c) vec a(b,vp(c)) #define vvp4(a, b, c, d) vec a(b,vp(c,d)) using vt = vector; #define _overloadvvt(_1, _2, _3, _4, name, ...) name #define vvt1(a) vec a #define vvt2(a, b) vec a(b) #define vvt3(a, b, c) vec a(b,vt(c)) #define vvt4(a, b, c, d) vec a(b,vt(c,d)) #define v3i(a, b, c, d) vector> a(b, vector(c, vi(d))) #define v3d(a, b, c, d) vector> a(b, vector(c, vd(d))) #define v3m(a, b, c, d) vector> a(b, vector(c, vm(d))) #define _vvi vector #define _vvl vector #define _vvb vector #define _vvs vector #define _vvd vector #define _vvc vector #define _vvp vector #define PQ priority_queue, greater > #define tos to_string using mapi = map; using mapd = map; using mapc = map; using maps = map; using seti = set; using setd = set; using setc = set; using sets = set; using qui = queue; #define bset bitset #define uset unordered_set #define mset multiset #define umap unordered_map #define mmap multimap //マクロ 繰り返し #define _overloadrep(_1, _2, _3, _4, name, ...) name # define _rep(i, n) for(int i = 0,_lim=n; i < _lim ; i++) #define repi(i, m, n) for(int i = m,_lim=n; i < _lim ; i++) #define repadd(i, m, n, ad) for(int i = m,_lim=n; i < _lim ; i+= ad) #define rep(...) _overloadrep(__VA_ARGS__,repadd,repi,_rep,)(__VA_ARGS__) #define _rer(i, n) for(int i = n; i >= 0 ; i--) #define reri(i, m, n) for(int i = m,_lim=n; i >= _lim ; i--) #define rerdec(i, m, n, dec) for(int i = m,_lim=n; i >= _lim ; i-=dec) #define rer(...) _overloadrep(__VA_ARGS__,rerdec,reri,_rer,)(__VA_ARGS__) #define fora(a, b) for(auto&& a : b) #define forg(gi, ve) for (int gi = 0, f, t, c; gi < ve.size() && (f = ve[gi].from, t = ve[gi].to, c = ve[gi].cost, true); gi++) #define fort(gi, ve) for (int gi = 0, f, t, c;gi> struct vector : std::vector { using std::vector::vector; typename std::vector::reference operator[](typename std::vector::size_type n) { return this->at(n); } }; } namespace std { template<> class hash> { public: size_t operator()(const std::pair &x) const { return hash()(((ll) x.first << 32) + x.second); } }; template<> class hash> { public: size_t operator()(const std::pair &x) const { return hash()(((ll) x.first << 32) + x.second); } }; } istream &operator>>(istream &iss, P &a) { iss >> a.first >> a.second; return iss; } template istream &operator>>(istream &iss, vector &vec) { for (T &x: vec) iss >> x; return iss; } ostream &operator<<(ostream &os, P p) { os << p.fi << " " << p.se; return os; } ostream &operator<<(ostream &os, T p) { os << p.f << " " << p.s << " " << p.t; return os; } ostream &operator<<(ostream &os, F p) { os << p.a << " " << p.b << " " << p.c << " " << p.d; return os; } template ostream &operator<<(ostream &os, vector &vec) { for (int i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " "); return os; } template ostream &operator<<(ostream &os, vector > &vec) { for (int i = 0; i < vec.size(); i++) { for (int j = 0; j < vec[0].size(); j++) { os << vec[i][j]; } os << endl; } return os; } template void resize(vector &vec, const H head) { //再帰の終端。 可変長templateの長さが 0 になるとこっちが呼ばれる。 vec.resize(head); } template void resize(vector &vec, const H &head, const T ... tail) { vec.resize(head); for (auto &v: vec) resize(v, tail...); } template T pop(set &set) { T res = *set.begin(); set.erase(set.find(res)); return res; } template T pop(mset &set) { T res = *set.begin(); set.erase(set.find(res)); return res; } template T popBack(set &set) { T res = *set.rbegin(); set.erase(set.find(res)); return res; } template T popBack(mset &set) { T res = *set.rbegin(); set.erase(set.find(res)); return res; } inline void sort(string &a) { sort(a.begin(), a.end()); } template inline void sort(vector &a) { sort(a.begin(), a.end()); }; template inline void sort(vector &a, int len) { sort(a.begin(), a.begin() + len); }; template inline void sort(vector &a, F f) { sort(a.begin(), a.end(), [&](T l, T r) { return f(l) < f(r); }); }; template inline void rsort(vector &a) { sort(a.begin(), a.end(), greater()); }; template inline void rsort(vector &a, int len) { sort(a.begin(), a.begin() + len, greater()); }; template inline void rsort(vector &a, F f) { sort(a.begin(), a.end(), [&](U l, U r) { return f(l) > f(r); }); }; template inline void sortp(vector &a, vector &b) { vp c; int n = sz(a); assert(n == sz(b)); rep(i, n)c.eb(a[i], b[i]); sort(c); rep(i, n) { a[i] = c[i].first; b[i] = c[i].second;; } }; template inline void sortp(vector &a, vector &b, F f) { vp c; int n = sz(a); assert(n == sz(b)); rep(i, n)c.eb(a[i], b[i]); sort(c, f); rep(i, n) { a[i] = c[i].first; b[i] = c[i].second; } }; template inline void rsortp(vector &a, vector &b) { vp c; int n = sz(a); assert(n == sz(b)); rep(i, n)c.eb(a[i], b[i]); rsort(c); rep(i, n) { a[i] = c[i].first; b[i] = c[i].second; } }; template inline void rsortp(vector &a, vector &b, F f) { vp c; int n = sz(a); assert(n == sz(b)); rep(i, n)c.eb(a[i], b[i]); rsort(c, f); rep(i, n) { a[i] = c[i].first; b[i] = c[i].second; } }; template inline void sortt(vector &a, vector &b, vector &c) { vt r; int n = sz(a); assert(n == sz(b)); assert(n == sz(c)); rep(i, n)r.eb(a[i], b[i], c[i]); sort(r); rep(i, n) { a[i] = r[i].f; b[i] = r[i].s; c[i] = r[i].t; } }; template inline void sortt(vector &a, vector &b, vector &c, F f) { vt r; int n = sz(a); assert(n == sz(b)); assert(n == sz(c)); rep(i, n)r.eb(a[i], b[i], c[i]); sort(r, f); rep(i, n) { a[i] = r[i].f; b[i] = r[i].s; c[i] = r[i].t; } }; template inline void rsortt(vector &a, vector &b, vector &c, F f) { vt r; int n = sz(a); assert(n == sz(b)); assert(n == sz(c)); rep(i, n)r.eb(a[i], b[i], c[i]); rsort(r, f); rep(i, n) { a[i] = r[i].f; b[i] = r[i].s; c[i] = r[i].t; } }; template inline void sort2(vector> &a) { for (int i = 0, n = a.size(); i < n; i++)sort(a[i]); } template inline void rsort2(vector> &a) { for (int i = 0, n = a.size(); i < n; i++)rsort(a[i]); } template void fill(A (&a)[N], const T &v) { rep(i, N)a[i] = v; } template void fill(A (&a)[N][O], const T &v) { rep(i, N)rep(j, O)a[i][j] = v; } template void fill(A (&a)[N][O][P], const T &v) { rep(i, N)rep(j, O)rep(k, P)a[i][j][k] = v; } template void fill(A (&a)[N][O][P][Q], const T &v) { rep(i, N)rep(j, O)rep(k, P)rep(l, Q)a[i][j][k][l] = v; } template void fill(A (&a)[N][O][P][Q][R], const T &v) { rep(i, N)rep(j, O)rep(k, P)rep(l, Q)rep(m, R)a[i][j][k][l][m] = v; } template void fill(A (&a)[N][O][P][Q][R][S], const T &v) { rep(i, N)rep(j, O)rep(k, P)rep(l, Q)rep(m, R)rep(n, S)a[i][j][k][l][m][n] = v; } template void fill(V &xx, const T vall) { xx = vall; } template void fill(vector &vecc, const T vall) { for (auto &&vx: vecc) fill(vx, vall); } //@汎用便利関数 入力 template T in() { T x; cin >> x; return (x); } string sin() { return in(); } double din() { return in(); } ll lin() { return in(); } #define na(a, n) a.resize(n); rep(i,n) cin >> a[i]; #define nao(a, n) a.resize(n+1); rep(i,n) cin >> a[i+1]; #define nad(a, n) a.resize(n); rep(i,n) cin >> a[i], a[i]--; #define na2(a, b, n) a.resize(n),b.resize(n);rep(i, n)cin >> a[i] >> b[i]; #define na2d(a, b, n) a.resize(n),b.resize(n);rep(i, n)cin >> a[i] >> b[i],a[i]--,b[i]--; #define na3(a, b, c, n) a.resize(n),b.resize(n),c.resize(n); rep(i, n)cin >> a[i] >> b[i] >> c[i]; #define na3d(a, b, c, n) a.resize(n),b.resize(n),c.resize(n); rep(i, n)cin >> a[i] >> b[i] >> c[i],a[i]--,b[i]--,c[i]--; #define nt(a, h, w) resize(a,h,w);rep(hi,h)rep(wi,w) cin >> a[hi][wi]; #define ntd(a, h, w) rs(a,h,w);rep(hi,h)rep(wi,w) cin >> a[hi][wi], a[hi][wi]--; #define ntp(a, h, w) fill(a,'#');rep(hi,1,h+1)rep(wi,1,w+1) cin >> a[hi][wi]; //汎用便利関数 出力 template void out(T x) { typeid(x) == typeid(double) ? cout << fixed << setprecision(10) << x << endl : cout << x << endl; } template void out(vector a) { fora(v, a)cout << v << endl; } //デバッグ #define sp << " " << #define debugName(VariableName) # VariableName #define _deb1(x) cerr << debugName(x)<<" = "< sets() { vec res(trees); umap map; rep(i, n) map[root(i)].push_back(i); int i = 0; for (auto &&p:map) { int r = p.fi; res[i].push_back(r); for (auto &&v:p.se) { if (r == v)continue; res[i].push_back(v); } i++; } return res; } }; //MOD関連 ll MOD = (int) 1e9 + 7; class mint { public: int x; mint() : x(0) {} mint(signed y) : x(y >= 0 ? y % MOD : MOD - (-y) % MOD) {} mint(int y) : x(y >= 0 ? y % MOD : MOD - (-y) % MOD) {} static int _mpow(int v, ll a) { ll x = v, n = a, res = 1; while (n) { if (n & 1)res = (res * x) % MOD; x = (x * x) % MOD; n >>= 1; } return res; } // Arithmetic Oprators mint &operator+=(mint that) { if ((x += that.x) >= MOD) x -= MOD; return *this; } mint &operator-=(mint that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; } mint &operator*=(mint that) { x = 1LL * x * that.x % MOD; return *this; } mint &operator/=(const mint &that); mint &operator^=(const mint &that) { this->x = _mpow(x, that.x); return *this; } mint &operator%=(mint that) { x %= that.x; return *this; } mint &operator+=(const int that) { return *this += mint(that); } mint &operator-=(const int that) { return *this -= mint(that); } mint &operator*=(const int that) { return *this *= mint(that); } mint &operator/=(const int that); mint &operator^=(const int that) { this->x = _mpow(x, that); return *this; } mint &operator%=(const int that) { return *this %= mint(that); } mint &operator+=(const signed that) { return *this += mint(that); } mint &operator-=(const signed that) { return *this -= mint(that); } mint &operator*=(const signed that) { return *this *= mint(that); } mint &operator/=(const signed that); mint &operator^=(const signed that) { this->x = _mpow(x, that); return *this; } mint &operator%=(const signed that) { return *this %= mint(that); } // Comparators bool operator<(mint that) { return x < that.x; } bool operator>(mint that) { return x > that.x; } bool operator<=(mint that) { return x <= that.x; } bool operator>=(mint that) { return x >= that.x; } bool operator!=(mint that) { return x != that.x; } bool operator==(mint that) { return x == that.x; } bool operator!=(int that) { return x != that; } bool operator==(int that) { return x == that; } bool operator!=(signed that) { return x != that; } bool operator==(signed that) { return x == that; } // Utilities unsigned getval() const { return x; } operator int() { return x; } mint operator+(mint that) const { return mint(*this) += that; } mint operator-(mint that) const { return mint(*this) -= that; } mint operator*(mint that) const { return mint(*this) *= that; } mint operator%(mint that) const { return mint(*this) %= that; } mint operator+(const int that) const { return mint(*this) += that; } mint operator-(const int that) const { return mint(*this) -= that; } mint operator*(const int that) const { return mint(*this) *= that; } mint operator%(const int that) const { return mint(*this) %= that; } mint operator=(const int that) { return *this = mint(that); } mint operator+(const signed that) const { return mint(*this) += that; } mint operator-(const signed that) const { return mint(*this) -= that; } mint operator*(const signed that) const { return mint(*this) *= that; } mint operator%(const signed that) const { return mint(*this) %= that; } mint operator=(const signed that) { return *this = mint(that); } mint operator++() { x++; return *this; } mint operator++(signed) { auto ret = *this; x++; return ret; } friend void operator+=(ll &a, const mint &b) { a = mint(a % MOD + b.x); } friend void operator-=(ll &a, const mint &b) { a = mint(a % MOD - b.x); } friend void operator*=(ll &a, const mint &b) { a = mint(a % MOD * b.x); } friend void operator/=(ll &a, const mint &b); friend mint operator+(const ll a, const mint &b) { return mint(a % MOD + b.x); } friend mint operator-(const ll a, const mint &b) { return mint(a % MOD - b.x); } friend mint operator*(const ll a, const mint &b) { return mint(a % MOD * b.x); } friend mint operator^(const ll a, const mint &b) { return _mpow(a, b.x); } }; mint itom(int v) { mint res; res.x = v; return res; } const int setModMax = 510000; vector fac, finv, inv; void setMod(int m = MOD) { fac.resize(setModMax); finv.resize(setModMax); inv.resize(setModMax); MOD = m; fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for (int i = 2; i < setModMax; i++) { fac[i] = fac[i - 1].x * i % MOD; inv[i] = MOD - inv[MOD % i].x * (MOD / i) % MOD; finv[i] = finv[i - 1].x * inv[i].x % MOD; } } mint mpow(int v, ll a) { return mint::_mpow(v, a); } mint com(ll n, ll r) { if (n < r || n < 0 || r < 0)return 0; if (fac.size() == 0)setMod(); return fac[n] * finv[r] * finv[n - r]; } mint ncr(ll n, ll r) { return com(n, r); } mint nhr(ll n, ll r) { return com(n + r - 1, r); } //拡張ユークリッドの互除法 mint minv(ll a) { if (fac[0] == 0)setMod(); if (a < setModMax) return inv[a]; a %= MOD; ll b = MOD, x = 1, y = 0; while (b) { ll t = a / b; a -= t * b; swap(a, b); x -= t * y; swap(x, y); } return x; } mint &mint::operator/=(const mint &that) { return *this *= minv(that.x); } mint &mint::operator/=(const ll a) { return *this *= minv(a); } mint &mint::operator/=(const signed a) { return *this *= minv(a); } void operator/=(ll &a, const mint &b) { a = (a * minv(b.x)).x; } using vm=vector; #define vvm(a, b, c) vec a(b,vm(c)) using PM = pair; vb isPrime; vi primes; void setPrime() { isPrime.resize(4010101); fill(isPrime, true); int len = sizeof(isPrime) / sizeof(isPrime[0]); isPrime[0] = isPrime[1] = false; for (int i = 2; i <= sqrt(len) + 5; ++i) { if (!isPrime[i])continue; for (int j = 2; i * j < len; ++j) { isPrime[i * j] = false; } } rep(i, len)if (isPrime[i])primes.pb(i); } //幾何 Pをcomplexとして扱う bool eq(double a, double b) { return fabs(a - b) < eps; } using C =complex; C rot(C &a, dou th) { return a * C(cos(th), sin(th)); } dou inpro(C &a, C &b) { return real(a * conj(b)); } //90度回転させて内積が0なら平行 bool line(C a, C b, C c) { C ab = b - a; C ac = c - a; //複素数の掛け算は回転 ab *= C(0, 1); return eq(inpro(ab, ac), 0); } bool line(P a, P b, P c) { return line(C(a.fi, a.se), C(b.fi, b.se), C(c.fi, c.se)); } bool line(int xa, int ya, int xb, int yb, int xc, int yc) { C a = C(xa, ya); C b = C(xb, yb); C c = C(xc, yc); return line(a, b, c); } //便利関数 //テスト用 char ranc() { return (char) ('a' + rand() % 26); } int rand(int min, int max) { assert(min <= max); if (min >= 0 && max >= 0) { return rand() % (max + 1 - min) + min; } else if (max < 0) { return -rand(-max, -min); } else { //+ if (rand() % 2) { return rand(0, max); //- } else { return -rand(0, -min); } } } vi ranv(int n, int min, int max) { vi v(n); rep(i, n)v[i] = rand(min, max); return v; } //単調増加 vi ranvi(int n, int min, int max) { vi v(n); bool bad = 1; while (bad) { bad = 0; v.resize(n); rep(i, n) { if (i && min > max - v[i - 1]) { bad = 1; break; } if (i)v[i] = v[i - 1] + rand(min, max - v[i - 1]); else v[i] = rand(min, max); } } return v; } void ranvlr(int n, int min, int max, vi &l, vi &r) { l.resize(n); r.resize(n); rep(i, n) { l[i] = rand(min, max); r[i] = l[i] + rand(0, max - l[i]); } } //便利 汎用 template int find(vector &a, const T key) { rep(i, sz(a))if (a[i] == key)return i; return -1; } template P find(vector> &a, const T key) { rep(i, sz(a)) rep(j, sz(a[0]))if (a[i][j] == key)return mp(i, j); return mp(-1, -1); } template T find(vector>> &a, const U key) { rep(i, sz(a))rep(j, sz(a[0]))rep(k, sz(a[0][0]))if (a[i][j][k] == key)return mt(i, j, k); return mt(-1, -1, -1); } template int count(V &a, const T k) { return a == k; } template int count(vector &a, const T k) { int ret = 0; fora(v, a)ret += count(v, k); return ret; } int mod(int a, int m) { return (a % m + m) % m; } int pow(int a) { return a * a; }; void iota(vector &ve, int s, int n) { ve.resize(n); iota(all(ve), s); } vi iota(int s, int n) { vi ve; ve.resize(n); iota(all(ve), s); return ve; } void ole() { #ifdef _DEBUG debugline("ole"); exit(0); #endif string a = "a"; rep(i, 30)a += a; rep(i, 1 << 17)cout << a << endl; cout << "OLE 出力長制限超過" << endl; exit(0); } void tle() { while (inf)cout << inf << endl; } ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } ll gcd(vi b) { ll res = b[0]; for (auto &&v :b)res = gcd(v, res); return res; } ll lcm(ll a, ll b) { return a / gcd(a, b) * b; } ll rev(ll a) { ll res = 0; while (a) { res *= 10; res += a % 10; a /= 10; } return res; } template vector rev(vector &a) { vector ret = a; reverse(all(ret)); return ret; } ll ceil(ll a, ll b) { if (b == 0) { debugline("ceil"); deb(a, b); ole(); return -1; } else return (a + b - 1) / b; } ll sqrt(ll a) { if (a < 0) { debugline("sqrt"); deb(a); ole(); } ll res = (ll) std::sqrt(a); while (res * res < a)res++; return res; } double log(double e, double x) { return log(x) / log(e); } ll sig(ll t) { return (1 + t) * t / 2; } ll sig(ll s, ll t) { return (s + t) * (t - s + 1) / 2; } vi divisors(int v) { vi res; for (int i = 1; i <= sqrt(v); ++i) { if (v % i == 0) { res.pb(i); if (i != v / i)res.pb(v / i); } } return res; } vi factorization(int v) { int tv = v; vi res; if (isPrime.size() == 0)setPrime(); for (auto &&p :primes) { if (v % p == 0)res.push_back(p); while (v % p == 0) { v /= p; } if (v == 1 || p * p > tv)break; } if (v > 1)res.pb(v); return res; } unordered_map factorizationMap(int v) { int tv = v; unordered_map res; if (isPrime.size() == 0)setPrime(); for (auto &&p :primes) { while (v % p == 0) { res[p]++; v /= p; } if (v == 1 || p * p > tv)break; } if (v > 1)res[v]++; return res; } int get(int a, int keta) { return (a / (int) pow(10, keta)) % 10; } int keta(int v) { int cou = 0; while (v) { cou++, v %= 10; } return cou; } template void imo(vector &v) { int n = v.size(); rep(i, n - 1)v[i + 1] += v[i]; } //変換系 template vector keys(vector> a) { vector res; for (auto &&k :a)res.pb(k.fi); return res; } template vector keys(map a) { vector res; for (auto &&k :a)res.pb(k.fi); return res; } template vector keys(umap a) { vector res; for (auto &&k :a)res.pb(k.fi); return res; } template vector values(vector> a) { vector res; for (auto &&k :a)res.pb(k.se); return res; } template vector values(map a) { vector res; for (auto &&k :a)res.pb(k.se); return res; } template vector values(umap a) { vector res; for (auto &&k :a)res.pb(k.se); return res; } vi list(int a) { vi res; while (a) { res.insert(res.begin(), a % 10); a /= 10; } return res; } template bool chmax(T &a, const U &b) { if (a < b) { a = b; return true; } return false; } template bool chmin(T &a, const U &b) { if (b < a) { a = b; return true; } return false; } template T min(T a, signed b) { return a < b ? a : b; } template T max(T a, signed b) { return a < b ? b : a; } template T min(T a, T b, T c) { return a >= b ? b >= c ? c : b : a >= c ? c : a; } template T max(T a, T b, T c) { return a <= b ? b <= c ? c : b : a <= c ? c : a; } template T min(vector a) { return *min_element(all(a)); } template T min(vector a, int n) { return *min_element(a.begin(), a.begin() + min(n, sz(a))); } template T min(vector a, int s, int n) { return *min_element(a.begin() + s, a.begin() + min(n, sz(a))); } template T max(vector a) { return *max_element(all(a)); } template T max(vector a, int n) { return *max_element(a.begin(), a.begin() + min(n, sz(a))); } template T max(vector a, int s, int n) { return *max_element(a.begin() + s, a.begin() + min(n, sz(a))); } template A max(A (&a)[N]) { A res = a[0]; rep(i, N)res = max(res, a[i]); return res; } template A max(A (&a)[N][O]) { A res = max(a[0]); rep(i, N)res = max(res, max(a[i])); return res; } template A max(A (&a)[N][O][P]) { A res = max(a[0]); rep(i, N)res = max(res, max(a[i])); return res; } template A max(A (&a)[N][O][P][Q], const T &v) { A res = max(a[0]); rep(i, N)res = max(res, max(a[i])); return res; } template A max(A (&a)[N][O][P][Q][R]) { A res = max(a[0]); rep(i, N)res = max(res, max(a[i])); return res; } template A max(A (&a)[N][O][P][Q][R][S]) { A res = max(a[0]); rep(i, N)res = max(res, max(a[i])); return res; } template A min(A (&a)[N]) { A res = a[0]; rep(i, N)res = min(res, a[i]); return res; } template A min(A (&a)[N][O]) { A res = min(a[0]); rep(i, N)res = min(res, max(a[i])); return res; } template A min(A (&a)[N][O][P]) { A res = min(a[0]); rep(i, N)res = min(res, min(a[i])); return res; } template A min(A (&a)[N][O][P][Q], const T &v) { A res = min(a[0]); rep(i, N)res = min(res, min(a[i])); return res; } template A min(A (&a)[N][O][P][Q][R]) { A res = min(a[0]); rep(i, N)res = min(res, min(a[i])); return res; } template A min(A (&a)[N][O][P][Q][R][S]) { A res = min(a[0]); rep(i, N)res = min(res, min(a[i])); return res; } template T sum(vector v, int len = -1) { if (len == -1)len = v.size(); T res = 0; chmin(len, v.size()); rep(i, len)res += v[i]; return res; } template T sum(vector> &v, int h = -1, int w = -1) { if (h == -1)h = v.size(); if (w == -1)w = v[0].size(); T res = 0; chmin(h, v.size()); chmin(w, v[0].size()); rep(i, h)rep(j, w)res += v[i][j]; return res; } P sump(vp &v, int len = -1) { if (len == -1)len = v.size(); P res = {0, 0}; chmin(len, v.size()); rep(i, len) { res.fi += v[i].fi; res.se += v[i].se; } return res; } ///要素が0の時、返り値は0か1か template T mul(vector &v, int len = -1) { if (len == -1)len = v.size(); T res = 1; chmin(len, v.size()); rep(i, len)res *= v[i]; return res; } void clear(PQ &q) { while (q.size())q.pop(); } template void clear(queue &q) { while (q.size())q.pop(); } template T *negarr(int size) { T *body = (T *) malloc((size * 2 + 1) * sizeof(T)); return body + size; } template T *negarr2(int h, int w) { double **dummy1 = new double *[2 * h + 1]; double *dummy2 = new double[(2 * h + 1) * (2 * w + 1)]; dummy1[0] = dummy2 + w; for (int i = 1; i <= 2 * h + 1; i++) { dummy1[i] = dummy1[i - 1] + 2 * w + 1; } double **a = dummy1 + h; } template struct ruic { const vector rui; ruic(vector &ru) : rui(ru) {} T operator()(int l, int r) { assert(l <= r); return rui[r] - rui[l]; } T operator[](int i) { return rui[i]; } }; template struct rruic { const T *rrui; rruic(T *ru) : rrui(ru) {} //n-1から-1へ T operator()(int l, int r) { assert(l >= r); return rrui[r] - rrui[l]; } T operator[](int i) { return rrui[i]; } }; //template vector ruiv(vector &a) template ruic ruiv(vector &a) { vector res(a.size() + 1); rep(i, a.size())res[i + 1] = res[i] + a[i]; return ruic(res); } template vector ruim(vector &a) { vector res(a.size() + 1, 1); rep(i, a.size())res[i + 1] = res[i] * a[i]; return res; } //template T *rrui(vector &a) { //右から左にかけての半開区間 (-1 n-1] template rruic rrui(vector &a) { int len = a.size(); T *body = (T *) malloc((len + 1) * sizeof(T)); T *res = body + 1; rer(i, len - 1)res[i - 1] = res[i] + a[i]; return rruic(res); } //掛け算 template T *rruim(vector &a) { int len = a.size(); T *body = (T *) malloc((len + 1) * sizeof(T)); T *res = body + 1; res[len - 1] = 1; rer(i, len - 1)res[i - 1] = res[i] * a[i]; return res; } template void inc(T &a, U v = 1) { a += v; } template void inc(vector &a, U v = 1) { for (auto &u :a)inc(u, v); } template void inc(vector &a) { for (auto &u :a)inc(u, 1); } template void dec(T &a, U v = 1) { a -= v; } template void dec(vector &a, U v = 1) { for (auto &u :a)dec(u, v); } template void dec(vector &a) { for (auto &u :a)dec(u, 1); } inline bool inside(int h, int w, int H, int W) { return h >= 0 && w >= 0 && h < H && w < W; } ll u(ll a) { return a < 0 ? 0 : a; } template vector u(const vector &a) { vector ret = a; fora(v, ret)v = u(v); return ret; } #define MIN(a) numeric_limits::min() #define MAX(a) numeric_limits::max() ll goldd(ll left, ll right, function calc) { double GRATIO = 1.6180339887498948482045868343656; ll lm = left + (ll) ((right - left) / (GRATIO + 1.0)); ll rm = lm + (ll) ((right - lm) / (GRATIO + 1.0)); ll fl = calc(lm); ll fr = calc(rm); while (right - left > 10) { if (fl < fr) { right = rm; rm = lm; fr = fl; lm = left + (ll) ((right - left) / (GRATIO + 1.0)); fl = calc(lm); } else { left = lm; lm = rm; fl = fr; rm = lm + (ll) ((right - lm) / (GRATIO + 1.0)); fr = calc(rm); } } ll minScore = MAX(ll); ll resIndex = left; for (ll i = left; i < right + 1; i++) { ll score = calc(i); if (minScore > score) { minScore = score; resIndex = i; } } return resIndex; } ll goldt(ll left, ll right, function calc) { double GRATIO = 1.6180339887498948482045868343656; ll lm = left + (ll) ((right - left) / (GRATIO + 1.0)); ll rm = lm + (ll) ((right - lm) / (GRATIO + 1.0)); ll fl = calc(lm); ll fr = calc(rm); while (right - left > 10) { if (fl > fr) { right = rm; rm = lm; fr = fl; lm = left + (ll) ((right - left) / (GRATIO + 1.0)); fl = calc(lm); } else { left = lm; lm = rm; fl = fr; rm = lm + (ll) ((right - lm) / (GRATIO + 1.0)); fr = calc(rm); } } if (left > right) { ll l = left; left = right; right = l; } ll maxScore = MIN(ll); ll resIndex = left; for (ll i = left; i < right + 1; i++) { ll score = calc(i); if (maxScore < score) { maxScore = score; resIndex = i; } } return resIndex; } template T min(vector> &a) { T res = MAX(T); rep(i, a.size())chmin(res, *min_element(all(a[i]))); return res; } template T max(vector> &a) { T res = MIN(T); rep(i, a.size())chmax(res, *max_element(all(a[i]))); return res; } bool bget(ll m, int keta) { return (m >> keta) & 1; } int bget(ll m, int keta, int sinsuu) { m /= (ll) pow(sinsuu, keta); return m % sinsuu; } inline ll bit(int n) { return (1LL << (n)); } inline ll bit(int n, int sinsuu) { return (ll) pow(sinsuu, n); } int bcou(ll m) { return __builtin_popcount(m & 0xFFFFFFFF) + __builtin_popcount(m >> 32); } //初期化は0を渡す ll nextComb(ll &mask, int n, int r) { if (!mask)return mask = (1LL << r) - 1; ll x = mask & -mask; //最下位の1 ll y = mask + x; //連続した下の1を繰り上がらせる ll res = ((mask & ~y) / x >> 1) | y; if (bget(res, n))return mask = 0; else return mask = res; } //n桁以下でビットがr個立っているもののvectorを返す vl bitCombList(int n, int r) { vl res; int m = 0; while (nextComb(m, n, r)) { res.pb(m); } return res; } //大文字小文字を区別する int altoiaZ(char c) { if ('A' <= c && c <= 'Z')return c - 'A'; return c - 'a' + 26; } char itoalaZ(int i) { if (i < 26)return 'A' + i; return 'a' + i - 26; } //aもAも0を返す 基本小文字 int altoi(char c) { if ('A' <= c && c <= 'Z')return c - 'A'; return c - 'a'; } char itoal(int i) { return 'a' + i; } int ctoi(char c) { return c - '0'; } char itoc(int i) { return i + '0'; } int vtoi(vi &v) { int res = 0; if (sz(v) > 18) { debugline("vtoi"); deb(sz(v)); ole(); } rep(i, sz(v)) { res *= 10; res += v[i]; } return res; } vi itov(int i) { vi res; while (i) { res.pb(i % 10); i /= 10; } rev(res); return res; } vector> ctoi(vector> s, char c) { int n = sz(s), m = sz(s[0]); vector> res(n, vector(m)); rep(i, n)rep(j, m)res[i][j] = s[i][j] == c; return res; } #define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() ); void compress(vi &a) { vi b; int len = a.size(); for (int i = 0; i < len; ++i) { b.push_back(a[i]); } sort(b); UNIQUE(b); for (int i = 0; i < len; ++i) { a[i] = lower_bound(all(b), a[i]) - b.begin(); } } void compress(int a[], int len) { vi b; for (int i = 0; i < len; ++i) { b.push_back(a[i]); } sort(b); UNIQUE(b); for (int i = 0; i < len; ++i) { a[i] = lower_bound(all(b), a[i]) - b.begin(); } } //要素が見つからなかったときに困る #define binarySearch(a, v) (binary_search(all(a),v)) #define lowerIndex(a, v) (lower_bound(all(a),v)-a.begin()) #define lowerBound(a, v) (*lower_bound(all(a),v)) #define upperIndex(a, v) (upper_bound(all(a),v)-a.begin()) #define upperBound(a, v) (*upper_bound(all(a),v)) #define ans(a) cout< inline void fin(T s) { cout << s << endl, exit(0); } template struct edge { int from, to; T cost; int id; int type; edge(int f, int t, T c = 1, int id = -1, int ty = -1) : from(f), to(t), cost(c), id(id), type(ty) {} bool operator<(const edge &b) const { return cost < b.cost; } bool operator>(const edge &b) const { return cost > b.cost; } }; template class graph { protected: vector _used; public : vector>> g; vector> edges; int n; graph(int n) : n(n) { g.resize(n), _used.resize(n); } void clear() { g.clear(), edges.clear(); } void resize(int n) { this->n = n; g.resize(n); _used.resize(n); } int size() { return g.size(); } vector > &operator[](int i) { return g[i]; } virtual void add(int from, int to, T cost, int id, int ty) = 0; virtual bool used(edge &e) = 0; virtual bool used(int id) = 0; virtual void del(edge &e) = 0; virtual void del(int id) = 0; }; template vector dijkstra(const graph &g, int s); template class digraph : public graph { public: using graph::g; using graph::n; using graph::edges; using graph::_used; digraph(int n) : graph(n) {} void add(int f, int t, T cost = 1, int id = -1, int ty = -1) { if (!(0 <= f && f < n && 0 <= t && t < n)) { debugline("digraph add"); deb(f, t, cost, id, ty); ole(); } if (id == -1)id = edges.size(); g[f].emplace_back(f, t, cost, id, ty); edges.emplace_back(f, t, cost, id, ty); } bool used(edge &e) { return _used[e.id]; } bool used(int id) { return _used[id]; } void del(edge &e) { _used[e.id] = _used[e.id ^ 1] = 1; } void del(int id) { _used[id] = _used[id ^ 1] = 1; } }; template class undigraph : public graph { public: using graph::g; using graph::n; using graph::edges; using graph::_used; undigraph(int n) : graph(n) { } void add(int f, int t, T cost = 1, int id = -1, int ty = -1) { if (!(0 <= f && f < n && 0 <= t && t < n)) { debugline("undigraph add"); deb(f, t, cost, id, ty); ole(); } if (id == -1)id = edges.size(); g[f].emplace_back(f, t, cost, id, ty); g[t].emplace_back(t, f, cost, id + 1, ty); edges.emplace_back(f, t, cost, id, ty); edges.emplace_back(t, f, cost, id + 1, ty); } void add(edge &e) { int f = e.from, t = e.to, ty = e.type; T cost = e.cost; add(f, t, cost, ty); } bool used(edge &e) { return _used[e.id]; } bool used(int id) { return _used[id]; } void del(edge &e) { _used[e.id] = _used[e.id ^ 1] = 1; } void del(int id) { _used[id] = _used[id ^ 1] = 1; } }; template class tree : public undigraph { public: using undigraph::g; using undigraph::n; using undigraph::edges; using undigraph::_used; vi dep; vi disv; private: bool never = 1; int root = -1; vector> par; bool costallone; void dfs(int v, int p, int d) { dep[v] = d; par[0][v] = p; int lim = (*this)[v].size(); for (int i = 0; i < lim; i++) { int t = g[v][i].to; if (t == p)con; dfs(t, v, d + 1); } } void built() { never = 0; n = g.size(); par.assign(30, vi(n)); dep.resize(n); costallone = 1; fora(e, edges)if (e.cost != 1)costallone = 0; dfs(root, -1, 0); rep(k, par.size() - 1) { rep(i, n) { if (par[k][i] == -1)par[k + 1][i] = -1; else par[k + 1][i] = par[k][par[k][i]]; } } if (costallone)disv = dep; else disv = dijkstra(*this, root); } int _lca(int u, int v) { if (dep[u] > dep[v])swap(u, v); rep(k, par.size()) { if ((dep[u] - dep[v]) >> k & 1) { v = par[k][v]; } } if (u == v)return u; rer(k, par.size() - 1) { if (par[k][u] != par[k][v]) { u = par[k][u]; v = par[k][v]; } } return par[0][u]; } int _dis(int u, int v) { int p = _lca(u, v); return disv[u] + disv[v] - disv[p] * 2; } public: tree(int n, int root = 0) : undigraph(n), root(root) {} bool leaf(int v) { return sz(g[v]) == 1 && v != root; } int dis(int u, int v) { if (never) { built(); } return _dis(u, v); } int lca(int u, int v) { if (never) { built(); } return _lca(u, v); } }; //辺によりメモリを大量消費 // よってedgesを消している //頂点10^6でメモリを190MB(制限の8割)使う //軽量化のため、辺を持たないbig gridクラスがあってもいいかもしれない // template class grid_k6 : public undigraph { public: using undigraph::g; using undigraph::n; using undigraph::edges; using undigraph::_used; int H, W; int eid = 0; void add(int f, int t, T cost = 1, int id = -1, int ty = -1) { if (!(0 <= f && f < n && 0 <= t && t < n)) { debugline("grid_k6 add"); deb(f, t, cost, id, ty); ole(); } g[f].emplace_back(f, t, cost, eid++, ty); g[t].emplace_back(t, f, cost, eid++, ty); } int getid(int h, int w) { if (!inside(h, w, H, W))return -1; return W * h + w; } P get2(int id) { return mp(id / W, id % W); } P operator()(int id) { return get2(id); } int operator()(int h, int w) { return getid(h, w); } grid_k6(int H, int W) : H(H), W(W), undigraph(H * W) { rep(h, H) { rep(w, W) { int f = getid(h, w); if (w + 1 < W) add(f, getid(h, w + 1)); if (h + 1 < H)add(f, getid(h + 1, w)); } } } grid_k6(_vvc ba, char wall = '#') : H(sz(ba)), W(sz(ba[0])), undigraph(sz(ba) * sz(ba[0])) { rep(h, H) { rep(w, W) { if (ba[h][w] == wall)con; int f = getid(h, w); if (w + 1 < W && ba[h][w + 1] != wall) { add(f, getid(h, w + 1)); } if (h + 1 < H && ba[h + 1][w] != wall) { add(f, getid(h + 1, w)); } } } } void add(int fh, int fw, int th, int tw) { add(getid(fh, fw), getid(th, tw)); } }; template bool nibu(const graph &g) { if (g.edges.size() == 0)return true; UnionFind uf(g.n * 2); for (auto &&e :g.edges)uf.unite(e.from, e.to + g.n), uf.unite(e.from + g.n, e.to); rep(i, g.n)if (uf.same(i, i + g.n))return 0; return 1; } //二部グラフを色分けした際の頂点数を返す template vp nibug(graph &g) { vp cg; if (!nibu(g)) { debugline("nibu"); ole(); } int _n = g.size(); vb _was(_n); queue

q; rep(i, _n) { if (_was[i])continue; q.push(mp(i, 1)); _was[i] = 1; int red = 0; int coun = 0; while (q.size()) { int now = q.front().fi; int col = q.front().se; red += col; coun++; q.pop(); forg(gi, g[now]) { if (_was[t])continue; q.push(mp(t, col ^ 1)); _was[t] = 1; } } cg.push_back(mp(red, coun - red)); } return cg; } template vector dijkstra(const graph &g, int s, int cant_arrive = -1) { if (!(0 <= s && s < g.n)) { debugline("dijkstra"); deb(s, g.n); ole(); } T initValue = MAX(T); vector dis(g.n, initValue); priority_queue, vector>, greater>> q; dis[s] = 0; q.emplace(0, s); while (q.size()) { T nowc = q.top().fi; int i = q.top().se; q.pop(); if (dis[i] != nowc)continue; for (auto &&e : g.g[i]) { int to = e.to; T cost = nowc + e.cost; if (dis[to] > cost) { dis[to] = cost; q.emplace(dis[to], to); } } } //たどり着かないなら-1 if (cant_arrive == -1)for (auto &&d :dis) if (d == initValue)d = -1; return dis; } //機能拡張 vp vtop(vi &a, vi &b) { vp res(sz(a)); rep(i, sz(a))res[i] = mp(a[i], b[i]); return res; } void ptov(vp &p, vi &a, vi &b) { a.resize(sz(p)); b.resize(sz(p)); rep(i, sz(p))a[i] = p[i].fi, b[i] = p[i].se; } template basic_string<_CharT, _Traits, _Alloc> operator+(const basic_string<_CharT, _Traits, _Alloc> &__lhs, const int __rv) { basic_string<_CharT, _Traits, _Alloc> __str(__lhs); __str.append(to_string(__rv)); return __str; } template void operator+=(basic_string<_CharT, _Traits, _Alloc> &__lhs, const int __rv) { __lhs += to_string(__rv); } template basic_string<_CharT, _Traits, _Alloc> operator+(const basic_string<_CharT, _Traits, _Alloc> &__lhs, const signed __rv) { basic_string<_CharT, _Traits, _Alloc> __str(__lhs); __str.append(to_string(__rv)); return __str; } template void operator+=(basic_string<_CharT, _Traits, _Alloc> &__lhs, const signed __rv) { __lhs += to_string(__rv); } template void operator+=(queue &a, U v) { a.push(v); } template priority_queue, greater > &operator+=(priority_queue, greater > &a, U v) { a.push(v); return a; } template priority_queue &operator+=(priority_queue &a, U v) { a.push(v); return a; } template set &operator+=(set &a, U v) { a.insert(v); return a; } template set> &operator+=(set> &a, U v) { a.insert(v); return a; } template vector &operator+=(vector &a, U v) { a.pb(v); return a; } template vector &operator+=(vector &a, vector &b) { a.pb(b); return a; } template vector &operator+=(vector &a, initializer_list v) { for (auto &&va :v)a.pb(va); return a; } template vector &operator-=(vector &a, vector &b) { if (sz(a) != sz(b)) { debugline("vector operator-="); deb(a); deb(b); ole(); } rep(i, sz(a))a[i] -= b[i]; return a; } template vector &operator-(vector &a, vector &b) { if (sz(a) != sz(b)) { debugline("vector operator-"); deb(a); deb(b); ole(); } vector res; rep(i, sz(a))res[i] = a[i] - b[i]; return res; } template void remove(vector &v, unsigned int i) { v.erase(v.begin() + i); } template void remove(vector &v, unsigned int s, unsigned int e) { v.erase(v.begin() + s, v.begin() + e); } template void removen(vector &v, unsigned int s, unsigned int n) { v.erase(v.begin() + s, v.begin() + s + n); } template void erase(vector &v, unsigned int i) { v.erase(v.begin() + i); } template void erase(vector &v, unsigned int s, unsigned int e) { v.erase(v.begin() + s, v.begin() + e); } template void erasen(vector &v, unsigned int s, unsigned int n) { v.erase(v.begin() + s, v.begin() + s + n); } template void insert(vector &v, unsigned int i, T t) { v.insert(v.begin() + i, t); } template void insert(vector &v, unsigned int i, vector list) { for (auto &&va :list)v.insert(v.begin() + i++, va); } template void insert(vector &v, initializer_list list) { for (auto &&va :list)v.pb(va); } template void insert(vector &v, unsigned int i, initializer_list list) { for (auto &&va :list)v.insert(v.begin() + i++, va); } template void insert(set &v, vector list) { for (auto &&va :list)v.insert(va); } template void insert(set &v, initializer_list list) { for (auto &&va :list)v.insert(va); } ll ma = numeric_limits::min(); ll mi = numeric_limits::max(); //閉路がなければtrue bool topo(vi &res, digraph &g) { int n = g.g.size(); vi nyu(n); rep(i, n)for (auto &&e :g[i])nyu[e.to]++; queue st; rep(i, n)if (nyu[i] == 0)st.push(i); while (st.size()) { int v = st.front(); st.pop(); res.pb(v); fora(e, g[v]) if (--nyu[e.to] == 0)st.push(e.to); } return res.size() == n; } //辞書順最小トポロジカルソート bool topos(vi &res, digraph &g) { int n = g.g.size(); vi nyu(n); rep(i, n)for (auto &&e :g[i])nyu[e.to]++; //小さい順 priority_queue, greater > q; rep(i, n)if (nyu[i] == 0)q.push(i); while (q.size()) { int i = q.top(); q.pop(); res.pb(i); fora(e, g[i])if (--nyu[e.to] == 0)q.push(e.to); } return res.size() == n; } vector split(const string a, const char deli) { string b = a + deli; int l = 0, r = 0, n = b.size(); vector res; rep(i, n) { if (b[i] == deli) { r = i; if (l < r)res.push_back(b.substr(l, r - l)); l = i + 1; } } return res; } vector split(const string a, const string deli) { string b = a + deli; int l = 0, r = 0, n = b.size(), dn = deli.size(); vector res; rep(i, n) { if (i + dn <= n && b.substr(i, i + dn) == deli) { r = i; if (l < r)res.push_back(b.substr(l, r - l)); i += dn - 1; l = i + 1; } } return res; } void yn(bool a) { if (a)cout << "yes" << endl; else cout << "no" << endl; } void Yn(bool a) { if (a)cout << "Yes" << endl; else cout << "No" << endl; } void YN(bool a) { if (a)cout << "YES" << endl; else cout << "NO" << endl; } void fyn(bool a) { if (a)cout << "yes" << endl; else cout << "no" << endl; exit(0); } void fYn(bool a) { if (a)cout << "Yes" << endl; else cout << "No" << endl; exit(0); } void fYN(bool a) { if (a)cout << "YES" << endl; else cout << "NO" << endl; exit(0); } void Possible(bool a) { if (a)cout << "Possible" << endl; else cout << "Impossible" << endl; exit(0); } int n, m, k, d, H, W, x, y, z, q; int cou; vi a, b, c; vvi (s, 0, 0); vvc (ba, 0, 0); vp p; template struct rolling_hash_secure { const int b[4] = {11731, 11839, 12239, 14407}; const int m[4] = {1000002571, 1000002631, 1000011277, 1000012187}; T s; vector hash[4], pow[4]; rolling_hash_secure(const T &S) : s(S) { int n = (int) S.size(); for (int i = 0; i < 4; ++i) { hash[i].assign(n + 1, 0); pow[i].assign(n + 1, 1); for (int j = 0; j < n; ++j) { hash[i][j + 1] = (hash[i][j] * b[i] + S[j]) % m[i]; pow[i][j + 1] = pow[i][j] * b[i] % m[i]; } } } // get hash of S[left:right] inline ll get(int l, int r, int id) const { ll res = hash[id][r] - hash[id][l] * pow[id][r - l] % m[id]; if (res < 0) res += m[id]; return res; } inline P get(int l, int r) { return mp((get(l, r, 0) << 32) | get(l, r, 1), (get(l, r, 2) << 32) | get(l, r, 3)); } inline P operator()(int l, int r) { return get(l, r); } // get lcp of S[a:] and S[b:] inline int lcp(int a, int b) const { int len = min((int) s.size() - a, (int) s.size() - b); int low = -1, high = len + 1; while (high - low > 1) { int mid = (low + high) / 2; if (get(a, a + mid, 0) != get(b, b + mid, 0)) high = mid; else if (get(a, a + mid, 1) != get(b, b + mid, 1)) high = mid; else low = mid; } return low; } // get lcp of S[a:] and T[b:] inline int lcp(const rolling_hash_secure &t, int a, int b) const { int len = min((int) s.size() - a, (int) s.size() - b); int low = -1, high = len + 1; while (high - low > 1) { int mid = (low + high) / 2; if (get(a, a + mid, 0) != get(b, b + mid, 0)) high = mid; else if (get(a, a + mid, 1) != get(b, b + mid, 1)) high = mid; else low = mid; } return low; } }; void solve() { str s = sin(); n = sz(s); rolling_hash_secure<> ro(s); vi dp(n + 1, -1); function rec = [&](int l, int r) { if (dp[l] != -1)return dp[l]; mint ret = 1;//[l r) rep(i, 1, n) { int ml = l + i; int mr = r - i; if (ml > mr)brk; if (ro(l, ml) == ro(mr, r))(ret += rec(ml, mr)) %= MOD; } return dp[l] = ret; }; cout << rec(0, n) << endl; } int my(int n, vi a) { return 0; } int sister(int n, vi a) { return 0; } signed main() { solve(); #define _arg n,a //cin>>n; //na(a,n); //my(_arg); //cout << my(_arg) << endl; #ifdef _DEBUG bool bad = 0; for (int i = 0, ok = 1; i < k5 && ok; i++) { int n = rand(1, 3); vi a = ranv(m, 1, 10); int myres = my(_arg); int res = sister(_arg); ok = myres == res; if (!ok) { cout << n << endl; cout << a << endl; cout << "正解 : " << res << endl; cout << "出力 : " << myres << endl; bad = 1; break; } } // if (!bad)cout << "お兄ちゃんすごい!天才!!" << endl; #endif return 0; };