#include using namespace std; //#include //using namespace atcoder; using ll=long long; using Graph=vector>; #define MOD 998244353 #define INF 1000000000 #define MAX 2000000 vector p; vector p_table(MAX+1,true); void prime(){ p_table.at(0)=false,p_table.at(1)=false; for(int i=2;i<=MAX;i++){ if(p_table.at(i)){ p.push_back(i); for(int j=2;i*j<=MAX;j++){ p_table.at(i*j)=false; } } } } ll modpow(ll a,ll n,ll mod){ ll res=1; while(n>0){ if(n&1){ //nのbitと...00001を比較 nが2で割り切れるならtrue res=(res*a)%mod; } a=(a*a)%mod; n>>=1; } return res; } ll modinv(ll a,ll mod){ return modpow(a,mod-2,mod); } ll fac[MAX],finv[MAX],inv[MAX]; void COMinit(){ fac[0]=fac[1]=1; finv[0]=finv[1]=1; inv[1]=1; for(int i=2;i>N; prime(); ll lcm=1; int n=p.size(); vector a(n); for(int i=0;iN){ break; } while(x*p[i]<=N){ x*=p[i]; } a[n]=x; lcm*=x; lcm%=MOD; } //cout<