#include "bits/stdc++.h" #include #include #include #define rep(i,n) for(int i = 0; i < n; i++) typedef long long ll; typedef unsigned long long ull; using namespace std; #define vll vector> #define vl vector #define vi vector #define vii vector> #define pb push_back #define pf push_front #define ld long double #define Sort(a) sort(a.begin(),a.end()) #define cSort(a,cmp) sort(a.begin(),a.end(),cmp) #define reSort(a) sort(a.rbegin(), a.rend()) static const ll llMAX = numeric_limits::max(); static const int intMAX = numeric_limits::max(); static const ll llMIN = numeric_limits::min(); static const int intMIN = numeric_limits::min(); static const ll d_5 = 100000; static const ll d9_7 = 1000000007; static const ll d_9 = 1000000000; static const double PI=3.14159265358979323846; template void Printvector(std::vector &a){ int size = a.size(); rep(i,size){ cout< void Printvector(std::vector> &a){ int size = a.size(); rep(i,size){ int size2=a[i].size(); rep(j,size2){ cout< vector getaccum(vector a){ int size=a.size(); vector ans(size); ans[0]=a[0]; for(int i=0;i vector> getaccum2D(vector> a){ int sizey=a.size(); int sizex=a[0].size(); vector> ans(sizey,vector(sizex,0)); //ans=a; ans[0][0]=a[0][0]; for(int i=1;i accum,int l,int r){//閉区間[l,r]の総和 if(l==0){ return accum[r]; }else{ return accum[r]-accum[l-1]; } } template T getaccumnum2D(vector>& accum,int x1,int y1,int x2,int y2){//2の方が右下、閉区間 T ans=accum[y2][x2]; if(x1==0 && y1==0){ ; }else if(x1>0 && y1==0){ ans-=accum[y2][x1-1]; }else if(x1==0 && y1>0){ ans-=accum[y1-1][x2]; }else{ ans-=accum[y1-1][x2]; ans-=accum[y2][x1-1]; ans+=accum[y1-1][x1-1]; } return ans; } ll digitpower(ll a,ll b){//aのb乗を計算 if(b==1){ return a; }else if(b==0){ return 1; } int mode=1; if(b%2==1){ ll tmp = digitpower(a,(b-1)/2); if(mode==1){ tmp%=d9_7; } tmp*=tmp; if(mode==1){ tmp%=d9_7; } tmp*=a; if(mode==1){ return tmp%d9_7; }else{ return tmp; } }else{ ll tmp = digitpower(a,(b)/2); if(mode==1){ tmp%=d9_7; } tmp*=tmp; if(mode==1){ tmp%=d9_7; } if(mode==1){ return tmp%d9_7; }else{ return tmp; } } } vl facs(2000010,-1); ll Factrial(ll num){ if(facs[num]!=-1){ return facs[num]; } if(num==1||num<=0){ return 1; }else if(num<0){ printf("ERROR_minus\n"); return 0; }else{ facs[num]=(num*Factrial(num-1))%d9_7; return facs[num]; } } long long modinv(long long a, long long m) {//modの逆元 long long b = m, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } u %= m; if (u < 0) u += m; return u; } /*vl invs(2000010,-1); ll linercomb(ll n,ll k, ll mod){//n,kの線形時間で求める if(n prime_factor(int64_t n) { unordered_map ret; for(int64_t i = 2; i * i <= n; i++) { while(n % i == 0) { ret[i]++; n /= i; } } if(n != 1) ret[n] = 1; return ret; } struct datas{ ll p; ll q; };/* bool cmp(const datas &a, const datas &b) { return a.num < b.num; }*/ template T gcd(T a,T b){ if(a==0){ return b; }else if(b==0){ return a; } while(1) { if(a < b) swap(a, b); if(!b) break; a %= b; } return a; } int LCS(string s,string t) { int n=s.size(); int m=t.size(); vector> dp=vector>(n+1,vector(m+1,0)); for (int i=0; i>b>>c>>d; b%=d9_7; c%=d9_7; //d%=d9_7; if(c==1){ d%=d9_7; cout<<(b*d)%d9_7<