//参考にしました:https://old.yosupo.jp/submission/33150 #include #include #define i64 long long using namespace std; const int mod=998244353; i64 pow(i64 a,i64 n,int mod){ if(n==1)return a; return pow(a*a%mod,n/2,mod)*(n%2?a:1)%mod; } vector sieve(int n){ vectortemp(n+1,true); vectorprimes; for(int i=2;i<=n;i++)if(temp[i]){ primes.push_back(i); for(int j=i+i;j<=n;j+=i)temp[j]=false; } return primes; } int main(){ i64 N,M; cin>>M>>N; const int sqrtN=(int)sqrtl(N); const vectorprimes=sieve(sqrtN); vectorpo(70); for(int i=1;i<70;i++)po[i]=pow(i,M,mod); auto f=[&](int,int e){return po[e+1];}; vectors(sqrtN+1),l(sqrtN+1); for(int i=1;i<=sqrtN;i++)s[i]=(i-1)*po[2]%mod; for(int i=1;i<=sqrtN;i++)l[i]=(N/i-1)%mod*po[2]%mod; for(int p:primes){ i64 p2=(i64)p*p,Np=N/p,t=sqrtN/p,u=min(sqrtN,N/p2),ss=s[p-1]; for(int i=1;i<=t;i++)(l[i]-=l[i*p]-ss)%=mod; for(int i=t+1;i<=u;i++)(l[i]-=s[Np/i]-ss)%=mod; for(int i=sqrtN;i>=p2;i--)(s[i]-=s[i/p]-ss)%=mod; } for(int p:boost::adaptors::reverse(primes)){ i64 p2=(i64)p*p,Np=N/p,t=sqrtN/p,u=min(sqrtN,N/p2),ss=s[p-1]; for(i64 i=p2;i<=sqrtN;i++)(s[i]+=(s[i/p]-ss)*f(p,1))%=mod; for(int i=u;i>=t+1;i--)(l[i]+=(s[Np/i]-ss)*f(p,1))%=mod; for(int i=t;i>=1;i--)(l[i]+=(l[i*p]-ss)*f(p,1))%=mod; } for(int i=1;i<=sqrtN;i++)s[i]++; for(int i=1;i<=sqrtN;i++)l[i]++; functionrec=[&](i64 n,int beg,i64 coef){ if(coef==0)return (i64)0; i64 ret=coef*(n>sqrtN?l[N/n]:s[n])%mod; for(int i=beg;i<(int)primes.size();i++){ i64 p=primes[i],nn=n/p/p; if(nn==0)break; for(int e=2;nn;nn/=p,e++){ (ret+=rec(nn,i+1,coef*(f(p,e)-f(p,1)*f(p,e-1)%mod)%mod))%=mod; } } return (i64)ret; }; cout << rec(N,0,1) << endl; }