#include using namespace std; #include using namespace atcoder; typedef long long ll; const long long INF = 1LL<<60; const double PI = acos(-1.0); /*const double PI = atan2(0.0,-1.0)*/ template inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } template inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } #define rep(i, n) for(ll i = 0; i < (ll)(n); i++) #define rep1(i,aa,n) for(ll i = aa; i <= (ll)(n); i++) #define ALL(a) (a).begin(),(a).end() #define v2d(val1,val2,ini) vector>(val1,vector(val2,ini)); #define v3d(val1,val2,val3,ini) vector>>(val1,vector>(val2,vector(val3,ini))); #define v4d(val1,val2,val3,val4,ini) vector>>>(val1,vector>>(val2,vector<>(val3,vector(val4,ini)))); #define pqe priority_queue #define pqeg priority_queue,greater> #define lcin(...) ll __VA_ARGS__;CINT(__VA_ARGS__) #define eout(...) COU(__VA_ARGS__); #define sout(...) SCOU(__VA_ARGS__); #define scin(...) string __VA_ARGS__;CINT(__VA_ARGS__) #define lb(aa,val) lower_bound(ALL(aa),val) #define pb push_back #define bpc __builtin_popcountll ll kaijou(ll e){ll r=1;rep(i,e){r*=(i+1);}return r;} bool kukan(ll t,ll a,ll b){ if(a<=t&&t<=b){ return true; }else return false; } void CINT(){} template void CINT(Head&& head,Tail&&... tail){ cin>>head; CINT(move(tail)...); } void COU(){} template void COU(Head&& head,Tail&&... tail){ cout< void SCOU(Head&& head,Tail&&... tail){ cout< T IN(){T x;cin>>x;return (x);} using pii = pair; using v2 = vector>; using v1 = vector; using v2p = vector>; using v1p = vector; const ll mo=1000000007; //const ll mo=998244353; ll mod_pow(ll N,ll n){ if(n==0) return 1; ll hh; hh=n%2; int tt=mod_pow(N,n/2); if(hh==0)return tt%mo*tt%mo; else {return tt%mo*tt%mo*N%mo;} } int main(){ //cout<