#include using namespace std; #define rep(i,a,b) for(ll i=a;i=b;i--) #define ll long long #define ull unsigned ll #define ld long double #define bl __int128_t #define fi first #define se second #define vel vector #define vvel vector #define pll pair #define vepll vector #define vvepll vector #define ves vector #define mint Mint<998244353> #define vem vector #define vvem vector #define pmm pair #define cleout(i) cout<using PQ=priority_queue,greater>; // 上 右 下 左 vector di={-1, 0, 1, 0}; vector dj={ 0, 1, 0,-1}; vector dx={ 0, 1, 0,-1}; vector dy={ 1, 0,-1, 0}; vector ddx={ 1, 1, 1, 0, -1, -1, -1, 0 }; vector ddy={ 1, 0, -1, -1, -1, 0, 1, 1 }; ll inf=1000000000000000000;//1e18 // LLONG_MAX mt19937_64 rng((ull)chrono::steady_clock::now().time_since_epoch().count()); template struct Mint{ ll num; static constexpr ll MOD=P; Mint(ll x=0){ if(x<0){ x*=-1; x%=P; x=P-x; } x%=P; num=x; } Mint operator+(const Mint &other)const{ return Mint(num+other.num); } Mint operator-(const Mint &other)const{ return Mint(num-other.num); } Mint operator*(const Mint &other)const{ return Mint(num*other.num); } Mint &operator+=(const Mint &other){ num+=other.num; if(num>=P) num-=P; return *this; } Mint &operator-=(const Mint &other){ num-=other.num; if(num<0) num+=P; return *this; } Mint &operator*=(const Mint &other){ num=(num*other.num)%P; return *this; } Mint beki(const ll &x)const{ Mint res=1; Mint now=num; rep(i,0,60){ if(x&(1ll<>(istream& is, Mint& m) { ll x; is>>x; m=Mint(x); return is; } }; /** * @brief 線形篩(素数・最小素因数・メビウス関数の列挙) * @details O(N)の計算量で[1,N)の範囲の素数、最小素因数、メビウス関数を同時に計算する。 * 実行後、グローバル変数の primes に素数リストが、minprime に最小素因数が格納される。 * @param N 探索する範囲の上限(N未満の値を計算する) * @return vel 各インデックスにおけるメビウス関数の値を格納した配列 */ vel primes; vel minprime; vel make_mobius(ll N){ minprime.assign(N,N); vel mobius(N,0); mobius[1]=1; rep(i,2,N){ if(minprime[i]>i){ minprime[i]=i; primes.push_back(i); mobius[i]=-1; } for(ll p:primes){ if(p*i>=N)break; minprime[p*i]=p; if(minprime[i]==p){//i=p*xとなってる mobius[p*i]=0; break; }else mobius[p*i]=-mobius[i]; } } return mobius; } struct CB{ vem n,r; CB(ll N){//N以下のものをmod INFで返す n.assign(N+1,1); r.assign(N+1,1); rep(i,2,N+1){ n.at(i)=n.at(i-1)*mint(i); } r.back()=n.back().inv(); rrep(i,N,0) r.at(i)=r.at(i+1)*(mint)(i+1); } mint comb(ll N,ll R){//NCR if(N>N>>M; vem ans(N+1,0); vem f(N+1); vel mob=make_mobius(N+1); rep(i,1,N+1){ ll now=1; while(now*i>_; else _=1; rep(__,0,_){ _solve(); } }