#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 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()); struct mint{ ll num; static ll P; static void set_mod(ll MOD){ P=MOD; } 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{ ll pos=x; mint res=1; mint now=num; while(pos){ if(pos&1){ res*=now; } now*=now; pos/=2; } return res; } mint inv()const{ mint res=1; mint now=num; rep(i,0,30){ if((P-2)&(1ll<>(istream& is,mint& m){ ll x; is>>x; m=mint(x); return is; } }; ll mint::P=998244353; //ll mint::P=1000000007; /** * @brief 線形篩(素数・最小素因数・メビウス関数の列挙) * @details O(N)の計算量で[1,N)の範囲の素数、最小素因数、メビウス関数を同時に計算する。 * 実行後、グローバル変数の primes に素数リストが、minprime に最小素因数が格納される。 * @param N 探索する範囲の上限(N未満の値を計算する) * @return vel 各インデックスにおけるメビウス関数の値を格納した配列 */ vel primes; vel minprime; vel make_mobius(vem &f,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; f[i]=(mint)(1-i); } for(ll p:primes){ if(p*i>=N)break; minprime[p*i]=p; if(minprime[i]==p){//i=p*xとなってる f[p*i]=f[i]; mobius[p*i]=0; break; }else{ f[p*i]=f[i]*(mint)(1-p); 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 f(N+1,1); vel mob=make_mobius(f,N+1); rep(i,1,N+1){ f[i]*=cb.r[i]*cb.n[i-1]; } auto g=[](ll i,ll N){ ll m=N/i; return (mint)(i*(m*(m+1))/2); }; mint cnt=0; rep(i,1,N+1){ cnt+=g(i,N)*g(i,M)*f[i]; } cout<>_; else _=1; rep(__,0,_){ _solve(); } }