#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #define _USE_MATH_DEFINES #include #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #include using namespace std; using namespace atcoder; using mint = modint1000000007; using mint2 = modint998244353; using ll = long long; using ld = long double; const ll MOD = 1e9 + 7; const ll MOD2 = 998244353LL; #define all(a) (a).begin(), (a).end() #define cin_vec(x) \ for (ll I1 = 0; I1 < x.size(); I1++) \ { \ cin >> x[I1]; \ } #define cout_vecn(x) \ for (ll I1 = 0; I1 < x.size(); I1++) \ { \ cout << x[I1] << endl; \ } #define cout_vec(x) \ for (ll I1 = 0; I1 < x.size(); I1++) \ { \ cout << x[I1] << " "; \ } \ cout << endl; ll powmod(ll a, ll n, ll mod) { ll res = 1; while (n > 0) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res; } ll gcd(ll x, ll y) { if (x < y) swap(x, y); // xの方が常に大きい ll r; while (y > 0) { r = x % y; x = y; y = r; } return x; } //オーバフローしないようにかける順番を気を付ける ll lcm(ll x, ll y) { return ll(x / gcd(x, y)) * y; } ll gcd_vec(vector const &A) { // N個の要素に対する最大公約数 ll size = (ll)A.size(); ll ret = A[0]; for (ll i = 1; i < size; i++) { ret = gcd(ret, A[i]); } return ret; } ll lcm_vec(vector const &A) { // N個の要素に対する最大公約数 ll size = A.size(); ll ret = A[0]; for (ll i = 1; i < size; i++) { ret = lcm(ret, A[i]); } return ret; } bool is_prime(ll N) { if (N == 1) return false; for (ll i = 2; i * i <= N; ++i) { if (N % i == 0) return false; } return true; } ll GetDigit(ll num) //桁数 { ll digit = 0; while (num != 0) { num /= 10; digit++; } return digit; } string convert(ll x, ll y) { string res; while (x > 0) { res.push_back('0' + (x % y)); x /= y; } reverse(res.begin(), res.end()); return res; } ll modinv(ll a, ll m) { ll b = m, u = 1, v = 0; while (b) { ll t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } u %= m; if (u < 0) u += m; return u; } using Graph = vector>; struct Edge { ll to; ll w; Edge(ll to, ll w) : to(to), w(w) {} }; //辺にコストがあるグラフ const int MAX = 200000; ll fact[MAX], inv_fact[MAX], inv[MAX]; ll Mod; void init(ll mod) { // 初期値設定と1はじまりインデックスに直す fact[0] = 1; fact[1] = 1; inv[0] = 1; inv[1] = 1; inv_fact[0] = 1; inv_fact[1] = 1; // メモの計算 for (int i = 2; i < MAX; i++) { // 階乗 fact[i] = fact[i - 1] * i % mod; // 逆元 inv[i] = mod - inv[mod % i] * (mod / i) % mod; // 逆元の階乗 inv_fact[i] = inv_fact[i - 1] * inv[i] % mod; } Mod = mod; } ll nCk(ll n, ll k) { if (n < k || k < 0) return 0; // 例外処理 return fact[n] * ((inv_fact[n - k] * inv_fact[k]) % Mod) % Mod; //二項係数の計算 } ll nHk(ll n, ll k) { if (n == 0 && k == 0) return 1; if (n < 0 || k < 0) return 0; return nCk(n + k - 1, k); } ll nPk(ll n, ll k) { if (n < k || k < 0) return 0; // 例外処理 return fact[n] * inv_fact[k] % Mod; //二項係数の計算 } string fix(ll x, ll y) { string s = to_string(x); string ans; for (int i = 0; i < y - s.size(); i++) { ans.push_back('0'); } ans += s; return ans; } vector> rle(vector s) { vector> vec; int cnt = 1; for (int i = 1; i < (int)s.size(); i++) { if (s[i] != s[i - 1]) { vec.push_back({s[i - 1], cnt}); cnt = 0; } cnt++; } vec.push_back({s[s.size() - 1], cnt}); return vec; } #define repa for (int i = 0; i < a; i++) #define rep(i, x, a) for (int(i) = (x); (i) < (a); (i)++) #define rep0(i, a) for (int(i) = 0; i < (a); (i)++) #define repaj(i) for (int(i) = 0; i < a; (i)++) // cout<>a>>b; a*=5;b*=18; if(a