#include typedef uint64_t u64; using namespace std; templateclass modint{ public: u64 val; constexpr modint(const u64 x=0) noexcept:val(x%mod){} constexpr u64 &value() noexcept{ return val; } constexpr const u64 &value() const noexcept{ return val; } constexpr modint operator+(const modint rhs) const noexcept{ return modint(*this)+=rhs; } constexpr modint operator-(const modint rhs) const noexcept{ return modint(*this)-=rhs; } constexpr modint operator*(const modint rhs) const noexcept{ return modint(*this)*=rhs; } constexpr modint operator/(const modint rhs) const noexcept{ return modint(*this)/=rhs; } constexpr modint &operator+=(const modint rhs) noexcept{ val+=rhs.val; if(val>=mod){ val-=mod; } return *this; } constexpr modint &operator-=(const modint rhs) noexcept{ if(val>=1; } return *this; } }; void scan(){} template void scan(T& n,Args&... args){ cin>>n; scan(args...); } template void scan_vec(T start,T end){ T now=start; for(;now!=end;++now){ cin>>(*now); } } void print(){} template void print(T n,Args... args){ cout< void println(T n){ cout< void println(T n,Args... args){ cout< void print_vec(T start,T end){ if(start!=end){ T now=start; cout<<(*now); ++now; for(;now!=end;++now){ cout<<' '<<(*now); } } cout< vector div_enum(T n){ vector res; for(T i=1;i*i<=n;++i){ if(n%i!=0){ continue; } res.push_back(i); if(i*i!=n){ res.push_back(n/i); } } sort(res.begin(),res.end()); return res; } template vector> prime_fact(T n){ vector> res; for(T i=2;i*i<=n;++i){ if(n%i!=0){ continue; } T ex=0; while(n%i==0){ n/=i; ex+=1; } res.push_back({i,ex}); } if(n!=1){ res.push_back({n,1}); } return res; } template T power(T a,U n) { T res=1; while(n){ res*=(n&1)?a:1; a*=a; n>>=1; } return res; } template struct combination { vector fact; combination(const int Max):fact(Max+1,1){ for(int i=2;i<=Max;++i){ fact[i]=fact[i-1]*(T)i; } } template T nCk(U n,U k){ if(n struct RSQ{ int N; vector bit; RSQ(int size):N(size+1),bit(size+1){}; void add(int a,T x){ a+=1; for(int i=a;i0;i-=(i&(-i))){ res+=bit[i]; } return res; } }; template struct RmQ{ const T INF=numeric_limits::max(); int n=-1; vector dat; RmQ(int n_):dat(n_*4,INF) { int x=1; while(x