API tools faq
paste
Advertisement
BaoJIaoPisu

Untitled

BaoJIaoPisu
Dec 28th, 2022
1,142
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 36.44 KB | None | 0 0
raw download clone embed print report
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. using ll = long long;
  6. using ld = long double;
  7. using ull = unsigned long long;
  8.  
  9. using pii = pair<int, int>;
  10. using pll = pair<ll, ll>;
  11. using pld = pair<ld, ld>;
  12.  
  13. #define fi first
  14. #define se second
  15. #define left BAO
  16. #define right ANH
  17. #define pb push_back
  18. #define pf push_front
  19. #define mp make_pair
  20. #define ins insert
  21. #define btpc __builtin_popcount
  22. #define btclz __builtin_clz
  23.  
  24. #define sz(x) (int)(x.size());
  25. #define all(x) x.begin(), x.end()
  26. #define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
  27.  
  28. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  29.  
  30. int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1};
  31. int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  32. int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};
  33.  
  34. template<class X, class Y>
  35.     bool minimize(X &x, const Y &y) {
  36.         if (x > y)
  37.         {
  38.             x = y;
  39.             return true;
  40.         }
  41.         return false;
  42.     }
  43. template<class X, class Y>
  44.     bool maximize(X &x, const Y &y) {
  45.         if (x < y)
  46.         {
  47.             x = y;
  48.             return true;
  49.         }
  50.         return false;
  51.     }
  52.  
  53. const int MOD = 1e9 + 7; //998244353
  54.  
  55. template<class X, class Y>
  56.     void add(X &x, const Y &y) {
  57.         x = (x + y);
  58.         if(x >= MOD) x -= MOD;
  59.     }
  60.  
  61. template<class X, class Y>
  62.     void sub(X &x, const Y &y) {
  63.         x = (x - y);
  64.         if(x < 0) x += MOD;
  65.     }
  66.  
  67. /* Author : Le Ngoc Bao Anh, 12A5, LQD High School for Gifted Student*/
  68.  
  69. const ll INF = 1e9;
  70. const int N = 1e7 + 10;
  71.  
  72. template <typename T> T mod_inv_in_range(T a, T m) {
  73.     // assert(0 <= a && a < m);
  74.     T x = a, y = m;
  75.     T vx = 1, vy = 0;
  76.      while (x) {
  77.         T k = y / x;
  78.         y %= x;
  79.         vy -= k * vx;
  80.         std::swap(x, y);
  81.         std::swap(vx, vy);
  82.     }
  83.     assert(y == 1);
  84.     return vy < 0 ? m + vy : vy;
  85. }
  86.  
  87. template <typename T> T mod_inv(T a, T m) {
  88.     a %= m;
  89.     a = a < 0 ? a + m : a;
  90.     return mod_inv_in_range(a, m);
  91. }
  92.  
  93. template <int MOD_> struct modnum {
  94.     static constexpr int MOD = MOD_;
  95.     static_assert(MOD_ > 0, "MOD must be positive");
  96.  
  97.     using ll = long long;
  98.  
  99.     int v;
  100.  
  101. public:
  102.  
  103.     modnum() : v(0) {}
  104.     modnum(ll v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
  105.     explicit operator int() const { return v; }
  106.     friend std::ostream& operator << (std::ostream& out, const modnum& n) { return out << int(n); }
  107.     friend std::istream& operator >> (std::istream& in, modnum& n) { ll v_; in >> v_; n = modnum(v_); return in; }
  108.  
  109.     friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
  110.     friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }
  111.  
  112.     modnum inv() const {
  113.         modnum res;
  114.         res.v = mod_inv_in_range(v, MOD);
  115.         return res;
  116.     }
  117.     friend modnum inv(const modnum& m) { return m.inv(); }
  118.     modnum neg() const {
  119.         modnum res;
  120.         res.v = v ? MOD-v : 0;
  121.         return res;
  122.     }
  123.     friend modnum neg(const modnum& m) { return m.neg(); }
  124.  
  125.     modnum operator- () const {
  126.         return neg();
  127.     }
  128.     modnum operator+ () const {
  129.         return modnum(*this);
  130.     }
  131.  
  132.     modnum& operator ++ () {
  133.         v ++;
  134.         if (v == MOD) v = 0;
  135.         return *this;
  136.     }
  137.     modnum& operator -- () {
  138.         if (v == 0) v = MOD;
  139.         v --;
  140.         return *this;
  141.     }
  142.     modnum& operator += (const modnum& o) {
  143.         v -= MOD-o.v;
  144.         v = (v < 0) ? v + MOD : v;
  145.         return *this;
  146.     }
  147.     modnum& operator -= (const modnum& o) {
  148.         v -= o.v;
  149.         v = (v < 0) ? v + MOD : v;
  150.         return *this;
  151.     }
  152.     modnum& operator *= (const modnum& o) {
  153.         v = int(ll(v) * ll(o.v) % MOD);
  154.         return *this;
  155.     }
  156.     modnum& operator /= (const modnum& o) {
  157.         return *this *= o.inv();
  158.     }
  159.  
  160.     friend modnum operator ++ (modnum& a, int) { modnum r = a; ++a; return r; }
  161.     friend modnum operator -- (modnum& a, int) { modnum r = a; --a; return r; }
  162.     friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
  163.     friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
  164.     friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
  165.     friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
  166. };
  167.  
  168. //ctto
  169. typedef complex<ld> pt;
  170. const ld PI = acos(-1.L);
  171.  
  172. template<class T> struct cplx {
  173.   T x, y;
  174.   cplx() {
  175.     x = 0.0;
  176.     y = 0.0;
  177.   }
  178.   cplx(T nx, T ny = 0) {
  179.     x = nx;
  180.     y = ny;
  181.   }
  182.   cplx operator+(const cplx &c) const {
  183.     return {x + c.x, y + c.y};
  184.   }
  185.   cplx operator-(const cplx &c) const {
  186.     return {x - c.x, y - c.y};
  187.   }
  188.   cplx operator*(const cplx &c) const {
  189.     return {x*c.x - y * c.y, x*c.y + y * c.x};
  190.   }
  191.   cplx& operator*=(const cplx &c) {
  192.     return *this = {x*c.x - y * c.y, x*c.y + y * c.x};
  193.   }
  194.   inline T real() const {
  195.     return x;
  196.   }
  197.   inline T imag() const {
  198.     return y;
  199.   }
  200.   // Only supports right scalar multiplication like p*c
  201.   template<class U> cplx operator*(const U &c) const {
  202.     return {x * c, y * c};
  203.   }
  204.   template<class U> cplx operator/(const U &c) const {
  205.     return {x / c, y / c};
  206.   }
  207.   template<class U> void operator/=(const U &c) {
  208.     x /= c;
  209.     y /= c;
  210.   }
  211. };
  212. #define polar(r,a)  (cplx<ld>){r*cos(a),r*sin(a)}
  213.  
  214. const int DIG = 9, FDIG = 4;
  215. const int BASE = 1e9, FBASE = 1e4;
  216. typedef cplx<ld> Cplx;
  217.  
  218.  
  219. // use mulmod when taking mod by int v and v>2e9
  220. // you can use mod by BigNum in that case too
  221. struct BigNum {
  222.   int sgn;
  223.   vector<int> a;
  224.   BigNum() : sgn(1) {}
  225.   BigNum(ll v) {
  226.     *this = v;
  227.   }
  228.   BigNum& operator = (ll v) {
  229.     sgn = 1;
  230.     if (v < 0) sgn = -1, v = -v;
  231.     a.clear();
  232.     for (; v > 0; v /= BASE) a.push_back(v % BASE);
  233.     return *this;
  234.   }
  235.   BigNum(const BigNum& other) {
  236.     sgn = other.sgn;
  237.     a = other.a;
  238.   }
  239.   friend void swap(BigNum& a, BigNum& b) {
  240.     swap(a.sgn, b.sgn);
  241.     swap(a.a, b.a);
  242.   }
  243.   BigNum& operator = (BigNum other) {
  244.     swap(*this, other);
  245.     return *this;
  246.   }
  247.   BigNum(BigNum&& other) : BigNum() {
  248.     swap(*this, other);
  249.   }
  250.   BigNum(const string& s) {
  251.     read(s);
  252.   }
  253.   void read(const string& s) {
  254.     sgn = 1;
  255.     a.clear();
  256.     int k = 0;
  257.     for (; k < s.size() && (s[k] == '-' || s[k] == '+'); k++)
  258.       if (s[k] == '-') sgn = -sgn;
  259.     for (int i = s.size() - 1; i >= k; i -= DIG) {
  260.       int x = 0;
  261.       for (int j = max(k, i - DIG + 1); j <= i; j++) x = x * 10 + s[j] - '0';
  262.       a.push_back(x);
  263.     }
  264.     trim();
  265.   }
  266.   friend istream& operator>>(istream &in, BigNum &v) {
  267.     string s;
  268.     in >> s;
  269.     v.read(s);
  270.     return in;
  271.   }
  272.   friend ostream& operator<<(ostream &out, const BigNum &v) {
  273.     if (v.sgn == -1 && !v.zero()) out << '-';
  274.     out << (v.a.empty() ? 0 : v.a.back());
  275.     for (int i = (int) v.a.size() - 2; i >= 0; --i)
  276.       out << setw(DIG) << setfill('0') << v.a[i];
  277.     return out;
  278.   }
  279.   bool operator<(const BigNum &v) const {
  280.     if (sgn != v.sgn) return sgn < v.sgn;
  281.     if (a.size() != v.a.size()) return a.size() * sgn < v.a.size() * v.sgn;
  282.     for (int i = (int)a.size() - 1; i >= 0; i--)
  283.       if (a[i] != v.a[i]) return a[i] * sgn < v.a[i] * sgn;
  284.     return 0;
  285.   }
  286.   bool operator>(const BigNum &v) const {
  287.     return v < *this;
  288.   }
  289.   bool operator<=(const BigNum &v) const {
  290.     return !(v < *this);
  291.   }
  292.   bool operator>=(const BigNum &v) const {
  293.     return !(*this < v);
  294.   }
  295.   bool operator==(const BigNum &v) const {
  296.     return !(*this < v) && !(v < *this);
  297.   }
  298.   bool operator!=(const BigNum &v) const {
  299.     return *this < v || v < *this;
  300.   }
  301.   friend int __cmp(const BigNum& x, const BigNum& y) {
  302.     if (x.a.size() != y.a.size()) return x.a.size() < y.a.size() ? -1 : 1;
  303.     for (int i = (int) x.a.size() - 1; i >= 0; --i) if (x.a[i] != y.a[i])
  304.         return x.a[i] < y.a[i] ? -1 : 1;
  305.     return 0;
  306.   }
  307.  
  308.   BigNum operator-() const {
  309.     BigNum res = *this;
  310.     if (zero()) return res;
  311.     res.sgn = -sgn;
  312.     return res;
  313.   }
  314.  
  315.   void __add(const BigNum& v) {
  316.     if (a.size() < v.a.size()) a.resize(v.a.size(), 0);
  317.     for (int i = 0, carry = 0; i < max(a.size(), v.a.size()) || carry; ++i) {
  318.       if (i == a.size()) a.push_back(0);
  319.       a[i] += carry + (i < (int) v.a.size() ? v.a[i] : 0);
  320.       carry = a[i] >= BASE;
  321.       if (carry) a[i] -= BASE;
  322.     }
  323.   }
  324.  
  325.   void __sub(const BigNum& v) {
  326.     for (int i = 0, carry = 0; i < (int) v.a.size() || carry; ++i) {
  327.       a[i] -= carry + (i < (int) v.a.size() ? v.a[i] : 0);
  328.       carry = a[i] < 0;
  329.       if (carry) a[i] += BASE;
  330.     }
  331.     this->trim();
  332.   }
  333.  
  334.   BigNum operator+=(const BigNum& v) {
  335.     if (sgn == v.sgn) __add(v);
  336.     else if (__cmp(*this, v) >= 0) __sub(v);
  337.     else {
  338.       BigNum vv = v;
  339.       swap(*this, vv);
  340.       __sub(vv);
  341.     }
  342.     return *this;
  343.   }
  344.  
  345.   BigNum operator-=(const BigNum& v) {
  346.     if (sgn == v.sgn) {
  347.       if (__cmp(*this, v) >= 0) __sub(v);
  348.       else {
  349.         BigNum vv = v;
  350.         swap(*this, vv);
  351.         __sub(vv);
  352.         sgn = -sgn;
  353.       }
  354.     } else __add(v);
  355.     return *this;
  356.   }
  357.  
  358.   template< typename L, typename R >
  359.   typename enable_if <
  360.   is_convertible<L, BigNum>::value &&
  361.   is_convertible<R, BigNum>::value &&
  362.   is_lvalue_reference < R&& >::value,
  363.   BigNum >::type friend operator + (L&& l, R&& r) {
  364.     BigNum result(forward<L>(l));
  365.     result += r;
  366.     return result;
  367.   }
  368.   template< typename L, typename R >
  369.   typename enable_if <
  370.   is_convertible<L, BigNum>::value &&
  371.   is_convertible<R, BigNum>::value &&
  372.   is_rvalue_reference < R&& >::value,
  373.   BigNum >::type friend operator + (L&& l, R&& r) {
  374.     BigNum result(move(r));
  375.     result += l;
  376.     return result;
  377.   }
  378.   template< typename L, typename R >
  379.   typename enable_if <
  380.   is_convertible<L, BigNum>::value &&
  381.   is_convertible<R, BigNum>::value,
  382.   BigNum >::type friend operator - (L&& l, R&& r) {
  383.     BigNum result(forward<L>(l));
  384.     result -= r;
  385.     return result;
  386.   }
  387.  
  388.   friend pair<BigNum, BigNum> divmod(const BigNum& a1, const BigNum& b1) {
  389.     ll norm = BASE / (b1.a.back() + 1);
  390.     BigNum a = a1.abs() * norm, b = b1.abs() * norm, q = 0, r = 0;
  391.     q.a.resize(a.a.size());
  392.     for (int i = a.a.size() - 1; i >= 0; i--) {
  393.       r *= BASE;
  394.       r += a.a[i];
  395.       ll s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()];
  396.       ll s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 1];
  397.       ll d = ((ll) BASE * s1 + s2) / b.a.back();
  398.       r -= b * d;
  399.       while (r < 0) r += b, --d;
  400.       q.a[i] = d;
  401.     }
  402.     q.sgn = a1.sgn * b1.sgn;
  403.     r.sgn = a1.sgn;
  404.     q.trim();
  405.     r.trim();
  406.     auto res = make_pair(q, r / norm);
  407.     if (res.second < 0) res.second += b1;
  408.     return res;
  409.   }
  410.   BigNum operator/(const BigNum &v) const {
  411.     return divmod(*this, v).first;
  412.   }
  413.   BigNum operator%(const BigNum &v) const {
  414.     return divmod(*this, v).second;
  415.   }
  416.   void operator/=(int v) {
  417.     if (llabs(v) >= BASE) {
  418.       *this /= BigNum(v);
  419.       return;
  420.     }
  421.     if (v < 0) sgn = -sgn, v = -v;
  422.     for (int i = (int) a.size() - 1, rem = 0; i >= 0; --i) {
  423.       ll cur = a[i] + rem * (ll)BASE;
  424.       a[i] = (int) (cur / v);
  425.       rem = (int) (cur % v);
  426.     }
  427.     trim();
  428.   }
  429.   BigNum operator/(int v) const {
  430.     if (llabs(v) >= BASE) return *this / BigNum(v);
  431.     BigNum res = *this;
  432.     res /= v;
  433.     return res;
  434.   }
  435.   void operator/=(const BigNum &v) {
  436.     *this = *this / v;
  437.   }
  438.   ll operator%(ll v) const {
  439.     int m = 0;
  440.     for (int i = a.size() - 1; i >= 0; --i) m = (a[i] + m * (ll) BASE) % v;
  441.     return m * sgn;
  442.   }
  443.   void operator*=(int v) {
  444.     if (llabs(v) >= BASE) {
  445.       *this *= BigNum(v);
  446.       return;
  447.     }
  448.     if (v < 0) sgn = -sgn, v = -v;
  449.     for (int i = 0, carry = 0; i < a.size() || carry; ++i) {
  450.       if (i == a.size()) a.push_back(0);
  451.       ll cur = a[i] * (ll) v + carry;
  452.       carry = (int) (cur / BASE);
  453.       a[i] = (int) (cur % BASE);
  454.     }
  455.     trim();
  456.   }
  457.   BigNum operator*(int v) const {
  458.     if (llabs(v) >= BASE) return *this * BigNum(v);
  459.     BigNum res = *this;
  460.     res *= v;
  461.     return res;
  462.   }
  463.  
  464.   static vector<int> convert_base(const vector<int> &a, int old_digits, int new_digits) {
  465.     vector<ll> p(max(old_digits, new_digits) + 1);
  466.     p[0] = 1;
  467.     for (int i = 1; i < (int) p.size(); i++)
  468.       p[i] = p[i - 1] * 10;
  469.     vector<int> res;
  470.     ll cur = 0;
  471.     int cur_digits = 0;
  472.     for (int i = 0; i < (int) a.size(); i++) {
  473.       cur += a[i] * p[cur_digits];
  474.       cur_digits += old_digits;
  475.       while (cur_digits >= new_digits) {
  476.         res.push_back((ll)(cur % p[new_digits]));
  477.         cur /= p[new_digits];
  478.         cur_digits -= new_digits;
  479.       }
  480.     }
  481.     res.push_back((int) cur);
  482.     while (!res.empty() && !res.back())
  483.       res.pop_back();
  484.     return res;
  485.   }
  486.  
  487.   void fft(vector<Cplx>& a, bool invert) const {
  488.     int n = a.size();
  489.     for (int i = 1, j = 0; i < n; ++i) {
  490.       int bit = n / 2;
  491.       for (; j >= bit; bit /= 2) j -= bit;
  492.       j += bit;
  493.       if (i < j) swap(a[i], a[j]);
  494.     }
  495.     for (int len = 2; len <= n; len *= 2) {
  496.       ld ang = 2 * PI / len * (invert ? -1 : 1);
  497.       Cplx wlen = polar(1, ang);
  498.       for (int i = 0; i < n; i += len) {
  499.         Cplx w(1);
  500.         for (int j = 0; j < len / 2; ++j) {
  501.           Cplx u = a[i + j], v = a[i + j + len / 2] * w;
  502.           a[i + j] = u + v;
  503.           a[i + j + len / 2] = u - v;
  504.           w *= wlen;
  505.         }
  506.       }
  507.     }
  508.     if (invert) for (int i = 0; i < n; ++i) a[i] /= n;
  509.   }
  510.   void multiply_fft(const vector<int> &a, const vector<int> &b, vector<int> &res) const {
  511.     vector<Cplx> fa(a.begin(), a.end()), fb(b.begin(), b.end());
  512.     int n = 1;
  513.     while (n < max(a.size(), b.size())) n *= 2;
  514.     n *= 2;
  515.     fa.resize(n);
  516.     fb.resize(n);
  517.     fft(fa, 0);
  518.     fft(fb, 0);
  519.     for (int i = 0; i < n; ++i) fa[i] *= fb[i];
  520.     fft(fa, 1);
  521.     res.resize(n);
  522.     ll carry = 0;
  523.     for (int i = 0; i < n; i++) {
  524.       ll t = (ll)(fa[i].real() + 0.5) + carry;
  525.       carry = t / FBASE;
  526.       res[i] = t % FBASE;
  527.     }
  528.   }
  529.   static inline int rev_incr(int a, int n) {
  530.     int msk = n / 2, cnt = 0;
  531.     while ( a & msk ) {
  532.       cnt++;
  533.       a <<= 1;
  534.     }
  535.     a &= msk - 1;
  536.     a |= msk;
  537.     while ( cnt-- ) a >>= 1;
  538.     return a;
  539.   }
  540.   static vector<Cplx> FFT(vector<Cplx> v, int dir = 1) {
  541.     Cplx wm, w, u, t;
  542.     int n = v.size();
  543.     vector<Cplx> V(n);
  544.     for (int k = 0, a = 0; k < n; ++k, a = rev_incr(a, n))
  545.       V[a] = v[k] / ld(dir > 0 ? 1 : n);
  546.     for (int m = 2; m <= n; m <<= 1) {
  547.       wm = polar( (ld)1, dir * 2 * PI / m );
  548.       for (int k = 0; k < n; k += m) {
  549.         w = 1;
  550.         for (int j = 0; j < m / 2; ++j, w *= wm) {
  551.           u = V[k + j];
  552.           t = w * V[k + j + m / 2];
  553.           V[k + j] = u + t;
  554.           V[k + j + m / 2] = u - t;
  555.         }
  556.       }
  557.     }
  558.     return V;
  559.   }
  560.   static void convolution(const vector<int>& a, const vector<int>& b, vector<int>& c) {
  561.     int sz = a.size() + b.size() - 1;
  562.     int n  = 1 << int(ceil(log2(sz)));
  563.     vector<Cplx> av(n, 0), bv(n, 0), cv;
  564.     for (int i = 0; i < a.size(); i++) av[i] = a[i];
  565.     for (int i = 0; i < b.size(); i++) bv[i] = b[i];
  566.     cv = FFT(bv);
  567.     bv = FFT(av);
  568.     for (int i = 0; i < n; i++) av[i] = bv[i] * cv[i];
  569.     cv = FFT(av, -1);
  570.     c.resize(n);
  571.     ll carry = 0;
  572.     for (int i = 0; i < n; i++) {
  573.       ll t = ll(cv[i].real() + 0.5) + carry;
  574.       carry = t / FBASE;
  575.       c[i] = t % FBASE;
  576.     }
  577.   }
  578.   BigNum mul_simple(const BigNum &v) const {
  579.     BigNum res;
  580.     res.sgn = sgn * v.sgn;
  581.     res.a.resize(a.size() + v.a.size());
  582.     for (int i = 0; i < a.size(); i++) if (a[i])
  583.         for (int j = 0, carry = 0; j < v.a.size() || carry; j++) {
  584.           ll cur = res.a[i + j] + (ll) a[i] * (j < v.a.size() ? v.a[j] : 0) + carry;
  585.           carry = (int) (cur / BASE);
  586.           res.a[i + j] = (int) (cur % BASE);
  587.         }
  588.     res.trim();
  589.     return res;
  590.   }
  591.   BigNum mul_fft(const BigNum& v) const {
  592.     BigNum res;
  593.     convolution(convert_base(a, DIG, FDIG), convert_base(v.a, DIG, FDIG), res.a);
  594.     res.a = convert_base(res.a, FDIG, DIG);
  595.     res.trim();
  596.     return res;
  597.   }
  598.   void operator*=(const BigNum &v) {
  599.     *this = *this * v;
  600.   }
  601.   BigNum operator*(const BigNum &v) const {
  602.     if (1LL * a.size() * v.a.size() <= 1000111) return mul_simple(v);
  603.     return mul_fft(v);
  604.   }
  605.  
  606.   BigNum abs() const {
  607.     BigNum res = *this;
  608.     res.sgn *= res.sgn;
  609.     return res;
  610.   }
  611.   void trim() {
  612.     while (!a.empty() && !a.back()) a.pop_back();
  613.   }
  614.   bool zero() const {
  615.     return a.empty() || (a.size() == 1 && !a[0]);
  616.   }
  617.   friend BigNum gcd(const BigNum &a, const BigNum &b) {
  618.     return b.zero() ? a : gcd(b, a % b);
  619.   }
  620. };
  621.  
  622. #define double long double
  623. namespace FFT {
  624.     const int maxf = 1 << 17;
  625.     struct cp {
  626.         double x, y;
  627.         cp(double x = 0, double y = 0) : x(x), y(y) {}
  628.         cp operator + (const cp& rhs) const {
  629.             return cp(x + rhs.x, y + rhs.y);
  630.         }
  631.         cp operator - (const cp& rhs) const {
  632.             return cp(x - rhs.x, y - rhs.y);
  633.         }
  634.         cp operator * (const cp& rhs) const {
  635.             return cp(x * rhs.x - y * rhs.y, x * rhs.y + y * rhs.x);
  636.         }
  637.         cp operator !() const {
  638.             return cp(x, -y);
  639.         }
  640.     } rts[maxf + 1];
  641.     cp fa[maxf], fb[maxf];
  642.     cp fc[maxf], fd[maxf];
  643.  
  644.     int bitrev[maxf];
  645.     void fftinit() {
  646.         int k = 0; while ((1 << k) < maxf) k++;
  647.         bitrev[0] = 0;
  648.         for (int i = 1; i < maxf; i++) {
  649.             bitrev[i] = bitrev[i >> 1] >> 1 | ((i & 1) << k - 1);
  650.         }
  651.         double PI = acos((double) -1.0);
  652.         rts[0] = rts[maxf] = cp(1, 0);
  653.         for (int i = 1; i + i <= maxf; i++) {
  654.             rts[i] = cp(cos(i * 2 * PI / maxf), sin(i * 2 * PI / maxf));
  655.         }
  656.         for (int i = maxf / 2 + 1; i < maxf; i++) {
  657.             rts[i] = !rts[maxf - i];
  658.         }
  659.     }
  660.     void dft(cp a[], int n, int sign) {
  661.         static int isinit;
  662.         if (!isinit) {
  663.             isinit = 1;
  664.             fftinit();
  665.         }
  666.         int d = 0; while ((1 << d) * n != maxf) d++;
  667.         for (int i = 0; i < n; i++) {
  668.             if (i < (bitrev[i] >> d)) {
  669.                 swap(a[i], a[bitrev[i] >> d]);
  670.             }
  671.         }
  672.         for (int len = 2; len <= n; len <<= 1) {
  673.             int delta = maxf / len * sign;
  674.             for (int i = 0; i < n; i += len) {
  675.                 cp *x = a + i,*y = a + i + (len >> 1), *w = sign > 0 ? rts : rts + maxf;
  676.                 for (int k = 0; k + k < len; k++) {
  677.                     cp z = *y * *w;
  678.                     *y = *x - z, *x = *x + z;
  679.                     x++, y++, w += delta;
  680.                 }
  681.             }
  682.         }
  683.         if (sign < 0) {
  684.             for (int i = 0; i < n; i++) {
  685.                 a[i].x /= n;
  686.                 a[i].y /= n;
  687.             }
  688.         }
  689.     }
  690.     void multiply(int a[], int b[], int na, int nb, long long c[], int dup = 0) {
  691.         int n = na + nb - 1; while (n != (n & -n)) n += n & -n;
  692.         for (int i = 0; i < n; i++) fa[i] = fb[i] = cp();
  693.         for (int i = 0; i < na; i++) fa[i] = cp(a[i]);
  694.         for (int i = 0; i < nb; i++) fb[i] = cp(b[i]);
  695.         dft(fa, n, 1);
  696.         if (dup) {
  697.             for (int i = 0; i < n; i++) fb[i] = fa[i];
  698.         }
  699.         else {
  700.             dft(fb, n, 1);
  701.         }
  702.         for (int i = 0; i < n; i++) fa[i] = fa[i] * fb[i];
  703.         dft(fa, n, -1);
  704.         for (int i = 0; i < n; i++) c[i] = (long long) floor(fa[i].x + 0.5);
  705.     }
  706.     void multiply(int a[], int b[], int na, int nb, int c[], int mod = (int) 1e9 + 7, int dup = 0) {
  707.         int n = na + nb - 1;
  708.         while (n != (n & -n)) n += n & -n;
  709.         for (int i = 0; i < n; i++) fa[i] = fb[i] = cp();
  710.         static const int magic = 15;
  711.         for (int i = 0; i < na; i++) fa[i] = cp(a[i] >> magic, a[i] & (1 << magic) - 1);
  712.         for (int i = 0; i < nb; i++) fb[i] = cp(b[i] >> magic, b[i] & (1 << magic) - 1);
  713.         dft(fa, n, 1);
  714.         if (dup) {
  715.             for (int i = 0; i < n; i++) fb[i] = fa[i];
  716.         }
  717.         else {
  718.             dft(fb, n, 1);
  719.         }
  720.         for (int i = 0; i < n; i++) {
  721.             int j = (n - i) % n;
  722.             cp x = fa[i] + !fa[j];
  723.             cp y = fb[i] + !fb[j];
  724.             cp z = !fa[j] - fa[i];
  725.             cp t = !fb[j] - fb[i];
  726.             fc[i] = (x * t + y * z) * cp(0, 0.25);
  727.             fd[i] = x * y * cp(0, 0.25) + z * t * cp(-0.25, 0);
  728.         }
  729.         dft(fc, n, -1), dft(fd, n, -1);
  730.         for (int i = 0; i < n; i++) {
  731.             long long u = ((long long) floor(fc[i].x + 0.5)) % mod;
  732.             long long v = ((long long) floor(fd[i].x + 0.5)) % mod;
  733.             long long w = ((long long) floor(fd[i].y + 0.5)) % mod;
  734.             c[i] = ((u << magic) + v + (w << magic + magic)) % mod;
  735.         }
  736.     }
  737.     vector<int> multiply(vector<int> a, vector<int> b, int mod = (int) 1e9 + 7) {
  738.         static int fa[maxf], fb[maxf], fc[maxf];
  739.         int na = a.size(), nb = b.size();
  740.         for (int i = 0; i < na; i++) fa[i] = a[i];
  741.         for (int i = 0; i < nb; i++) fb[i] = b[i];
  742.         multiply(fa, fb, na, nb, fc, mod, a == b);
  743.         int k = na + nb - 1;
  744.         vector<int> res(k);
  745.         for (int i = 0; i < k; i++) res[i] = fc[i];
  746.         return res;
  747.     }
  748.     int fpow(int a, int k, int p) {
  749.         if (!k) return 1;
  750.         int res = a, t = a; k--;
  751.         while (k) {
  752.             if (k & 1) res = (long long) res * t % p;
  753.             t = (long long) t * t % p;
  754.             k >>= 1;
  755.         }
  756.         return res;
  757.     }
  758.     vector<int> invert(vector<int> a, int n, int mod){
  759.         assert(a[0] != 0);
  760.         vector<int> x(1, fpow(a[0], mod - 2, mod));
  761.         while (x.size() < n) {
  762.             vector<int> tmp(a.begin(), a.begin() + min(a.size(), 2 * x.size()));
  763.             vector<int> nx = multiply(multiply(x, x, mod), tmp, mod);
  764.             x.resize(2 * x.size());
  765.             for (int i = 0; i < x.size(); i++) {
  766.                 x[i] += x[i];
  767.                 x[i] -= nx[i];
  768.                 if (x[i] < 0) x[i] += mod;
  769.                 if (x[i] >= mod) x[i] -= mod;
  770.             }
  771.         }
  772.         x.resize(n);
  773.         return x;
  774.     }
  775.     pair<vector<int>, vector<int> > divmod(vector<int> a, vector<int> b, int mod) {
  776.         int n = a.size(), m = b.size();
  777.         if (n < m) {
  778.             return make_pair(vector<int>(), a);
  779.         }
  780.         reverse(a.begin(), a.end());
  781.         reverse(b.begin(), b.end());
  782.         vector<int> rb = invert(b, n - m + 1, mod);
  783.         vector<int> d = multiply(a, rb, mod);
  784.         reverse(a.begin(), a.end());
  785.         reverse(b.begin(), b.end());
  786.         while (d.size() > n - m + 1) d.pop_back();
  787.         reverse(d.begin(), d.end());
  788.         vector<int> r = multiply(d, b, mod);
  789.         while (r.size() >= m) r.pop_back();
  790.         for (int i = 0; i < m; i++) {
  791.             r[i] = a[i] - r[i];
  792.             if (r[i] < 0) r[i] += mod;
  793.         }
  794.         return make_pair(d, r);
  795.     }
  796.     vector<int> chirpz_transform(vector<int> a, int z, int k, int mod) {
  797.         int n = a.size();
  798.         vector<int> x;
  799.         vector<int> y;
  800.         int iz = fpow(z, mod - 2, mod);
  801.         for (int i = 0; i < n; i++) {
  802.             x.push_back((long long) a[i] * fpow(z, (long long) i * i, mod) % mod);
  803.         }
  804.         for (int i = 1 - n; i < k; i++) {
  805.             y.push_back(fpow(iz, (long long) i * i, mod));
  806.         }
  807.         vector<int> r = FFT::multiply(x, y, mod);
  808.         vector<int> res(k);
  809.         for (int i = 0; i < k; i++) {
  810.             res[i] = (long long) r[i + n - 1] * fpow(z, (long long) i * i, mod) % mod;
  811.         }
  812.         return res;
  813.     }
  814. }
  815. #undef double
  816.  
  817. struct MFMC {
  818.     //O(n ^ 2 * m ^ 2)
  819.  
  820.     struct Edge {
  821.         int u, v;
  822.         ll cap, cost;
  823.  
  824.         Edge() : u(), v(), cap(), cost() {}
  825.         Edge(int _u, int _v, ll _cap, ll _cost) : u(_u), v(_v), cap(_cap), cost(_cost) {}
  826.     };
  827.  
  828.     vector<Edge> ed;
  829.     vector<vector<int>> g;
  830.     vector<ll> dist;
  831.     vector<bool> inq;
  832.     vector<int> p;
  833.     int n;
  834.     int S, T;
  835.  
  836.     MFMC() : n(), S(), T() {}
  837.     MFMC(int _n, int _S, int _T) {
  838.         n = _n;
  839.         S = _S;
  840.         T = _T;
  841.         g.resize(n + 3);
  842.         dist.resize(n + 3);
  843.         inq.resize(n + 3);
  844.         p.resize(n + 3);
  845.         ed = vector<Edge>();
  846.         for(int i = 0; i < n; i++) g[i].clear();
  847.     }
  848.  
  849.     void addEdge(int u, int v, ll cap, ll cost) {
  850.         g[u].pb(ed.size());
  851.         ed.pb(Edge(u, v, cap, cost));
  852.         g[v].pb(ed.size());
  853.         ed.pb(Edge(v, u, 0, -cost));
  854.     }
  855.  
  856.     bool spfa() {
  857.         for(int i = 0; i <= n; i++) {
  858.             dist[i] = INF;
  859.             inq[i] = false;
  860.             p[i] = -1;
  861.         }        
  862.  
  863.         dist[S] = 0;
  864.         queue<int> q;
  865.         q.push(S); inq[S] = true;
  866.  
  867.         while(!q.empty()) {
  868.             int u = q.front(); q.pop(); inq[u] = false;
  869.             for(int i = 0; i < (int)g[u].size(); i++) {
  870.                 Edge e = ed[g[u][i]];
  871.                 if(!e.cap) continue;
  872.                 if(dist[e.v] > dist[u] + e.cost) {
  873.                     dist[e.v] = dist[u] + e.cost;
  874.                     p[e.v] = g[u][i];
  875.                     if(!inq[e.v]) {
  876.                         q.push(e.v);
  877.                         inq[e.v] = true;
  878.                     }
  879.                 }
  880.             }
  881.         }
  882.  
  883.         return (p[T] >= 0);
  884.     }
  885.  
  886.     pll Flow() {
  887.         //return (maxflow, cost)
  888.         ll flow = 0, cost = 0;
  889.         while(spfa()) {
  890.             int u = T;
  891.  
  892.             ll f = INF;
  893.             while(u != S) {
  894.                 f = min(f, ed[p[u]].cap);
  895.                 u = ed[p[u]].u;
  896.             }
  897.  
  898.             flow += f; cost += f * dist[T];
  899.             u = T;
  900.             while(u != S) {
  901.                 ed[p[u]].cap -= f;
  902.                 ed[p[u] ^ 1].cap += f;
  903.                 u = ed[p[u]].u;
  904.             }
  905.         }
  906.  
  907.         return make_pair(flow, cost);
  908.     }
  909. };
  910.  
  911. struct Dinitz {
  912.     struct Edges {
  913.         int u, v;
  914.         ll cap;
  915.  
  916.         Edges() : u(), v(), cap() {}
  917.         Edges(int _u, int _v, ll _cap) : u(_u), v(_v), cap(_cap) {}
  918.     };
  919.  
  920.     vector<vector<int>> g;
  921.     vector<Edges> ed;
  922.     vector<int> dist;
  923.     vector<int> id;
  924.     int S, T;
  925.     int n;
  926.  
  927.     Dinitz() : ed(), n(), S(), T() {}
  928.     Dinitz(int _n, int _S, int _T) {
  929.         n = _n; S = _S; T = _T;
  930.         g.resize(n);
  931.         dist.resize(n);
  932.         id.resize(n);
  933.         for(int i = 0; i < n; i++) g[i].clear();
  934.         ed = vector<Edges>();
  935.     }
  936.  
  937.     void addEdge(int u, int v, ll cap) {
  938.         g[u].pb((int)ed.size());
  939.         ed.pb(Edges(u, v, cap));
  940.         g[v].pb((int)ed.size());
  941.         ed.pb(Edges(v, u, 0));
  942.     }
  943.  
  944.     bool bfs() {
  945.         for(int i = 0; i < n; i++) dist[i] = n + 5;
  946.         queue<int> q;
  947.         q.push(S); dist[S] = 0;
  948.         while(!q.empty()) {
  949.             int u = q.front(); q.pop();
  950.             for(int i : g[u]) {
  951.                 Edges e = ed[i];
  952.                 if(!e.cap) continue;
  953.                 if(dist[e.v] <= dist[u] + 1) continue;
  954.                 dist[e.v] = dist[u] + 1;
  955.                 q.push(e.v);
  956.             }
  957.         }
  958.  
  959.         return dist[T] < n + 5;
  960.     }
  961.  
  962.     ll dfs(int u, ll flow) {
  963.         if(u == T || flow == 0) return flow;
  964.  
  965.         ll ans = 0;
  966.         for(int &i = id[u]; i < (int)g[u].size(); i++) {
  967.             Edges e = ed[g[u][i]];
  968.             if(!e.cap) continue;
  969.             if(dist[e.v] != dist[u] + 1) continue;
  970.             ll f = dfs(e.v, min(flow, e.cap));
  971.             flow -= f;
  972.             ans += f;
  973.             ed[g[u][i]].cap -= f;
  974.             ed[g[u][i] ^ 1].cap += f;
  975.             if(flow == 0) return ans;
  976.         }
  977.  
  978.         return ans;
  979.     }
  980.  
  981.     ll Flow() {
  982.         ll ans = 0;
  983.         while(bfs()) {
  984.             for(int i = 0; i < n; i++) id[i] = 0;
  985.             ans += dfs(S, INF * INF);
  986.         }
  987.  
  988.         return ans;
  989.     }
  990. };
  991.  
  992. struct TWOSAT {
  993.     int n;
  994.     vector<vector<int>> g;
  995.     vector<vector<int>> ed;
  996.     vector<int> Num;
  997.     vector<int> Low;
  998.     vector<int> idComp;
  999.     vector<bool> visited;
  1000.     stack<int> st;
  1001.     vector<int> ord;
  1002.     vector<int> idSort;
  1003.     int Time, cntComp;
  1004.  
  1005.     TWOSAT(int _n = 0) {
  1006.         n = _n;
  1007.         g.resize(2 * n + 2);
  1008.         ed.resize(2 * n + 2);
  1009.         Num.resize(2 * n + 2);
  1010.         Low.resize(2 * n + 2);
  1011.         visited.resize(2 * n + 2);
  1012.         idComp.resize(2 * n + 2);
  1013.         idSort.resize(2 * n + 2);
  1014.         ord.clear();
  1015.         Time = cntComp = 0;
  1016.  
  1017.         for(int i = 1; i <= 2 * n; i++) {
  1018.             g[i].clear(); ed[i].clear();
  1019.             idSort[i] = Num[i] = visited[i] = Low[i] = idComp[i] = 0;
  1020.         }
  1021.     }
  1022.  
  1023.     int NOT(int u) {
  1024.         return (u > n ? u - n : u + n);
  1025.     }
  1026.  
  1027.     void Connect(int u, int v) {
  1028.         g[u].pb(v);
  1029.     }
  1030.  
  1031.     void addEdge(int u, int v) {
  1032.         // u || v = 1
  1033.         Connect(NOT(u), v);
  1034.         Connect(NOT(v), u);
  1035.     }
  1036.  
  1037.     void tarjan(int u) {
  1038.         Num[u] = Low[u] = ++Time;
  1039.         st.push(u);
  1040.  
  1041.         for(auto v : g[u]) {
  1042.             if(Num[v]) {
  1043.                 Low[u] = min(Low[u], Num[v]);
  1044.             } else {
  1045.                 tarjan(v);
  1046.                 Low[u] = min(Low[u], Low[v]);
  1047.             }
  1048.         }
  1049.  
  1050.         if(Num[u] == Low[u]) {
  1051.             int v = 0;
  1052.             ++cntComp;
  1053.             do {
  1054.                 v = st.top(); st.pop();
  1055.                 idComp[v] = cntComp;
  1056.                 Num[v] = Low[v] = INF;
  1057.             } while(v != u);
  1058.         }
  1059.     }
  1060.  
  1061.     void topo(int u) {
  1062.         visited[u] = true;
  1063.         for(auto v : ed[u]) {
  1064.             if(!visited[v]) topo(v);
  1065.         }
  1066.  
  1067.         ord.pb(u);
  1068.     }
  1069.  
  1070.     vector<int> do2SAT() {
  1071.         for(int i = 1; i <= 2 * n; i++) {
  1072.             if(!Num[i]) tarjan(i);
  1073.         }
  1074.  
  1075.         for(int i = 1; i <= n; i++) {
  1076.             if(idComp[i] == idComp[i + n]) return {-1};
  1077.         }
  1078.  
  1079.         vector<int> ans;
  1080.         for(int i = 1; i <= 2 * n; i++) {
  1081.             int u = idComp[i];
  1082.             for(auto v : g[i]) {
  1083.                 v = idComp[v];
  1084.                 if(u == v) continue;
  1085.                 ed[u].pb(v);
  1086.             }    
  1087.         }
  1088.  
  1089.         for(int i = 1; i <= cntComp; i++) {
  1090.             if(!visited[i]) topo(i);
  1091.         }
  1092.         reverse(all(ord));
  1093.  
  1094.         for(int i = 0; i < cntComp; i++) idSort[ord[i]] = i + 1;
  1095.  
  1096.         for(int i = 1; i <= n; i++) {
  1097.             int u = idComp[i], v = idComp[i + n];
  1098.             if(idSort[u] > idSort[v]) ans.pb(i);
  1099.         }
  1100.  
  1101.         return ans;
  1102.     }
  1103. };
  1104.  
  1105. struct LiChaoTree {
  1106.     int n;
  1107.     struct Line {
  1108.         ll a = 0, b = INF * INF;
  1109.  
  1110.         Line(ll _a = 0, ll _b = 0) : a(_a), b(_b) {}
  1111.     };
  1112.  
  1113.     vector<Line> Node;
  1114.  
  1115.     LiChaoTree(int _n = 0) {
  1116.         n = _n;
  1117.         Node.resize(4 * n + 7);
  1118.     }
  1119.  
  1120. private:    
  1121.     ll f(Line u, ll x) {return u.a * x + u.b;}
  1122.  
  1123.     void AddLine(Line u, int L, int R, int id) {
  1124.         int mid = (L + R) >> 1;
  1125.         bool left = f(u, L) < f(Node[id], L);
  1126.         bool m = f(u, mid) < f(Node[id], mid);
  1127.  
  1128.         if(m) swap(u, Node[id]);
  1129.  
  1130.         if(L == R) return;
  1131.         if(m != left) AddLine(u, L, mid, id << 1);
  1132.         else AddLine(u, mid + 1, R, id << 1 | 1);
  1133.     }
  1134.  
  1135.     ll Get(int L, int R, int x, int id) {
  1136.         if(L > x || R < x) return INF * INF;
  1137.         int mid = (L + R) >> 1;
  1138.  
  1139.         ll ans = f(Node[id], x);
  1140.  
  1141.         if(L == R) return ans;
  1142.         if(x <= mid) minimize(ans, Get(L, mid, x, id << 1));
  1143.         else minimize(ans, Get(mid + 1, R, x, id << 1 | 1));
  1144.         return ans;
  1145.     }
  1146.  
  1147. public:
  1148.     void addLine(ll a, ll b) {
  1149.         AddLine(Line(a, b), 1, n, 1);
  1150.     }
  1151.  
  1152.     ll get(int x) {
  1153.         return Get(1, n, x, 1);
  1154.     }
  1155. };
  1156.  
  1157. struct ConvexHullTrick {
  1158.     struct Line {
  1159.         ll a, b;
  1160.  
  1161.         Line(ll _a = 0, ll _b = -INF * INF) : a(_a), b(_b) {};
  1162.     };
  1163.    
  1164.     deque<pair<Line, int>> Convex;
  1165.    
  1166.     ll f(Line u, ll x) {return u.a * x + u.b;}
  1167.  
  1168.     ll find_inter(Line u, Line v) {
  1169.         return (v.b - u.b + u.a - v.a - 1) / (u.a - v.a);
  1170.     }
  1171.  
  1172.     void add(ll a, ll b) {
  1173.         Line u = Line(a, b);
  1174.         while(Convex.size()) {
  1175.             Line v = Convex.back().fi;
  1176.             ll x = find_inter(u, v);
  1177.             if(x <= Convex.back().se) {
  1178.                 Convex.pop_back();
  1179.             } else {
  1180.                 Convex.pb(mp(u, x));
  1181.                 return;
  1182.             }
  1183.         }
  1184.  
  1185.         Convex.pb(mp(u, 0));
  1186.     }
  1187.  
  1188.     ll get(ll x) {
  1189.         while(Convex.size() > 1) {
  1190.             pair<Line, int> v = Convex.front();
  1191.             Convex.pop_front();
  1192.             if(x >= Convex.front().se) continue;
  1193.             else {
  1194.                 Convex.pf(v);
  1195.                 break;
  1196.             }
  1197.         }
  1198.  
  1199.         if(Convex.empty()) return -INF * INF;
  1200.         return f(Convex.front().fi, x);
  1201.     }
  1202. };
  1203.  
  1204. vector<int> z_function(string s) {
  1205.     int n = (int) s.length();
  1206.     vector<int> z(n);
  1207.     for (int i = 1, l = 0, r = 0; i < n; ++i) {
  1208.         if (i <= r)
  1209.             z[i] = min (r - i + 1, z[i - l]);
  1210.         while (i + z[i] < n && s[z[i]] == s[i + z[i]])
  1211.             ++z[i];
  1212.         if (i + z[i] - 1 > r)
  1213.             l = i, r = i + z[i] - 1;
  1214.     }
  1215.     return z;
  1216. }
  1217.  
  1218. #include <stdio.h>
  1219. #include <string.h>
  1220.  
  1221. #include <algorithm>
  1222. #include <iostream>
  1223. #include <string>
  1224. using namespace std;
  1225.  
  1226. bool maximize(int &a, int b) {
  1227.     if (a < b)
  1228.         a = b;
  1229.     else
  1230.         return false;
  1231.     return true;
  1232. }
  1233.  
  1234. void prepare(char a[], char b[]) {
  1235.     int cnt = 0;
  1236.     b[++cnt] = '#';
  1237.     for (int i = 1; a[i]; i++) {
  1238.         b[++cnt] = a[i];
  1239.         b[++cnt] = '#';
  1240.     }
  1241.     b[++cnt] = 0;
  1242.     b[0] = '^';
  1243. }
  1244.  
  1245. int manacher(char b[]) {
  1246.     int C = 1, R = 1, n = strlen(b + 1);
  1247.     int *P = new int[n + 2], r = 0;
  1248.  
  1249.     for (int i = 2; i < n; i++) {
  1250.         int i_mirror = 2 * C - i;
  1251.         P[i] = (R > i) ? min(R - i, P[i_mirror]) : 0;
  1252.         while (b[i - 1 - P[i]] == b[i + 1 + P[i]]) P[i]++;
  1253.         maximize(r, P[i]);
  1254.         if (i + P[i] > R) {
  1255.             C = i;
  1256.             R = i + P[i];
  1257.         }
  1258.     }
  1259.     delete[] P;
  1260.     return r;
  1261. }
  1262.  
  1263. using num = modnum<MOD>;
  1264.  
  1265. string B = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
  1266.  
  1267. int id[300];
  1268. bool a[N];
  1269. int cnt[10000][2];
  1270. num pref[N][2], suff[N][2];
  1271. int prv[N], nxt[N];
  1272. int last[2];
  1273.  
  1274. void BaoJiaoPisu() {
  1275.     int n; cin >> n;
  1276.     string s; cin >> s;
  1277.  
  1278.     for(int i = 0; i < 64; i++) id[B[i]] = i;
  1279.  
  1280.     int sz = 0;
  1281.     for(int i = 0; i < s.size(); i++) {
  1282.         int x = id[s[i]];
  1283.         for(int j = 0; j < 6; j++) {
  1284.             a[++sz] = (x >> j & 1);
  1285.         }
  1286.     }
  1287.  
  1288.     if(n <= 1e3) {
  1289.         for(int i = 1; i <= n; i++) {
  1290.             cnt[i][0] = cnt[i - 1][0] + (a[i] == 0);
  1291.             cnt[i][1] = cnt[i - 1][1] + (a[i] == 1);
  1292.         }
  1293.  
  1294.         ll ans = 0;
  1295.         for(int i = 1; i <= n; i++) {
  1296.             for(int j = i; j <= n; j++) {
  1297.                 int x = cnt[j][1] - cnt[i - 1][1];
  1298.                 int y = cnt[j][0] - cnt[i - 1][0];
  1299.                 if(!x) ans += 1ll * y * y;
  1300.                 else if(!y) ans += 1ll * x * x;
  1301.                 else ans += 1ll * x * y;
  1302.                 ans %= MOD;
  1303.             }
  1304.         }
  1305.  
  1306.         cout << ans;
  1307.         return;
  1308.     }
  1309.  
  1310.     for(int i = 1; i <= n; i++) {
  1311.         int x = a[i];
  1312.         prv[i] = last[x ^ 1];
  1313.         last[x] = i;
  1314.     }
  1315.  
  1316.     last[0] = last[1] = n + 1;
  1317.     for(int i = n; i >= 1; i--) {
  1318.         int x = a[i];
  1319.         nxt[i] = last[x ^ 1];
  1320.         last[x] = i;
  1321.     }
  1322.  
  1323.     for(int i = 1; i <= n; i++) {
  1324.         pref[i][0] = pref[i - 1][0];
  1325.         pref[i][1] = pref[i - 1][1];
  1326.         int x = a[i];
  1327.         pref[i][x] += i;
  1328.     }
  1329.  
  1330.     for(int i = n; i >= 1; i--) {
  1331.         suff[i][0] = suff[i + 1][0];
  1332.         suff[i][1] = suff[i + 1][1];
  1333.         int x = a[i];
  1334.         suff[i][x] += n - i + 1;
  1335.     }
  1336.  
  1337.     num ans = 0;
  1338.     num inv2 = num(1) / num(2);
  1339.     for(int i = 1; i <= n; i++) {
  1340.         num l = i - prv[i] - 1;
  1341.         num r = nxt[i] - i;
  1342.         ans += l * (l + 1) * inv2 * r;
  1343.         ans += r * (r + 1) * inv2 * (l + 1);
  1344.         int x = a[i];
  1345.         if(!x) continue;
  1346.         ans += pref[i][x ^ 1] * num(n - i + 1);
  1347.         ans += suff[i][x ^ 1] * num(i);
  1348.  
  1349.     }
  1350.  
  1351.     cout << ans;
  1352. }
  1353.  
  1354. int main()
  1355. {
  1356.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  1357.     #ifndef ONLINE_JUDGE
  1358.     freopen("input.txt", "r", stdin);
  1359.     freopen("output.txt", "w", stdout);
  1360.     #else
  1361.     //online
  1362.     freopen("DYSLEXIA.inp", "r", stdin);
  1363.     freopen("DYSLEXIA.out", "w", stdout);
  1364.     #endif
  1365.  
  1366.     int tc = 1, ddd = 0;
  1367.     // cin >> tc;
  1368.     while(tc--) {
  1369.         //ddd++;
  1370.         //cout << "Case #" << ddd << ": ";
  1371.         BaoJiaoPisu();
  1372.     }
  1373. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!