#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=0; 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 bprime(P+200); ll searchprime(ll max){//発見した素因数の個数を返す //max+=180; bprime[1]=false; // cout<<"rrr"<>n>>k; vector ntos={2,8,5,7,1,4}; int nsize=n.size(); int ksize=k.size(); int ans=0; rep(i,nsize){ ans+=n[i]-'0'; ans%=6; ans*=10; } ans/=10; int tmpk=0; rep(i,ksize){ tmpk+=k[i]-'0'; tmpk%=6; tmpk*=10; } tmpk/=10; ll ans2=digitpower((ll)ans,(ll)tmpk); ans2%=6; ans2+=5; ans2%=6; cout<