class Prime: def __init__(self,N): assert N<=10**8 self.smallest_prime_factor=[None]*(N+1) for i in range(2,N+1,2): self.smallest_prime_factor[i]=2 n=int(N**.5)+1 for p in range(3,n,2): if self.smallest_prime_factor[p]==None: self.smallest_prime_factor[p]=p for i in range(p**2,N+1,2*p): if self.smallest_prime_factor[i]==None: self.smallest_prime_factor[i]=p for p in range(n,N+1): if self.smallest_prime_factor[p]==None: self.smallest_prime_factor[p]=p self.primes=[p for p in range(N+1) if p==self.smallest_prime_factor[p]] def Factorize(self,N): assert N>=1 factors=defaultdict(int) if N<=len(self.smallest_prime_factor)-1: while N!=1: factors[self.smallest_prime_factor[N]]+=1 N//=self.smallest_prime_factor[N] else: for p in self.primes: while N%p==0: N//=p factors[p]+=1 if N
0 divisors=[1] for p,e in self.Factorize(N).items(): pow_p=[1] for _ in range(e): pow_p.append(pow_p[-1]*p) divisors=[i*j for i in divisors for j in pow_p] return divisors def Is_Prime(self,N): return N==self.smallest_prime_factor[N] def Totient(self,N): for p in self.Factorize(N).keys(): N*=p-1 N//=p return N def Mebius(self,N): fact=self.Factorize(N) for e in fact.values(): if e>=2: return 0 else: if len(fact)%2==0: return 1 else: return -1 def Multiplicative_Prefix_Sum(N,F,f,mod=0): Pr=Prime(int(N**.5)) def Lucy_DP(N,F): f_1=F(2)-F(1) if mod: f_1%=mod inv_f_1=pow(f_1,mod-2,mod) dp={} Qn=[N] while Qn[-1]: Qn.append(N//(N//Qn[-1]+1)) if f_1: for x in Qn: if x>1: dp[x+1]=F(x+1)-F(2) if mod: dp[x+1]%=mod else: dp[x+1]=0 for p in Pr.primes: f_p=F(p+1)-F(p) if mod: f_p%=mod for x in Qn: if p*p>x: break if mod: dp[x+1]-=(dp[x//p+1]-dp[p])*f_p%mod*inv_f_1%mod dp[x+1]%=mod else: dp[x+1]-=(dp[x//p+1]-dp[p])*f_p//f_1 else: for x in Qn: dp[x+1]=0 return dp def Black_Algorithm(N,f,F_prime): P=[] x=1 f_x=[[f(2,0,1)]] retu=f_x[-1][0]+F_prime[N+1] if mod: retu%=mod queue=[] for i,p in enumerate(Pr.primes): queue.append((p,i,1)) queue.append((p,i,0)) while queue: p,ip,t=queue.pop() if t==0: x*=p if P and P[-1][0]==p: P[-1][1]+=1 P[-1][2]*=p f_x[-1].append(f_x[-2][-1]*f(*P[-1])) else: P.append([p,1,p]) f_x.append([f_x[-1][-1]*f(p,1,p)]) if mod: f_x[-1][-1]%=mod p,e,pe=P[-1] if mod: retu+=f_x[-2][-1]*f(p,e+1,pe*p)%mod retu+=f_x[-1][-1]*(F_prime[N//x+1]-F_prime[p+1])%mod retu%=mod else: retu+=f_x[-2][-1]*f(p,e+1,pe*p) retu+=f_x[-1][-1]*(F_prime[N//x+1]-F_prime[p+1]) for i in range(ip,len(Pr.primes)): q=Pr.primes[i] if x*q*q>N: break queue.append((q,i,1)) queue.append((q,i,0)) else: x//=P[-1][0] P[-1][1]-=1 P[-1][2]//=p f_x[-1].pop() if P[-1][1]==0: P.pop() f_x.pop() return retu F_prime=Lucy_DP(N,F) return Black_Algorithm(N,f,F_prime) N,M=map(int,input().split()) mod=998244353 pow2N=pow(2,N,mod) def F(x): return (x-1)*pow2N pow_N=[pow(i,N,mod) for i in range(100)] def f(p,e,pe): return pow_N[e+1] ans=Multiplicative_Prefix_Sum(M,F,f,mod) print(ans)