結果
問題 | No.1962 Not Divide |
ユーザー |
![]() |
提出日時 | 2023-05-04 08:36:30 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 480 ms / 2,000 ms |
コード長 | 39,820 bytes |
コンパイル時間 | 316 ms |
コンパイル使用メモリ | 86,784 KB |
実行使用メモリ | 85,104 KB |
最終ジャッジ日時 | 2024-11-22 03:11:41 |
合計ジャッジ時間 | 6,678 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
import sysreadline=sys.stdin.readlinedef Tonelli_Shanks(N,p):if pow(N,p>>1,p)==p-1:retu=Noneelif p%4==3:retu=pow(N,(p+1)//4,p)else:for nonresidue in range(1,p):if pow(nonresidue,p>>1,p)==p-1:breakpp=p-1cnt=0while pp%2==0:pp//=2cnt+=1s=pow(N,pp,p)retu=pow(N,(pp+1)//2,p)for i in range(cnt-2,-1,-1):if pow(s,1<<i,p)==p-1:s*=pow(nonresidue,p>>1+i,p)s%=pretu*=pow(nonresidue,p>>2+i,p)retu%=preturn retu#mod = 998244353imag = 911660635iimag = 86583718rate2 = (911660635, 509520358, 369330050, 332049552, 983190778, 123842337, 238493703, 975955924, 603855026, 856644456, 131300601,842657263, 730768835, 942482514, 806263778, 151565301, 510815449, 503497456, 743006876, 741047443, 56250497, 867605899)irate2 = (86583718, 372528824, 373294451, 645684063, 112220581, 692852209, 155456985, 797128860, 90816748, 860285882, 927414960,354738543, 109331171, 293255632, 535113200, 308540755, 121186627, 608385704, 438932459, 359477183, 824071951, 103369235)rate3 = (372528824, 337190230, 454590761, 816400692, 578227951, 180142363, 83780245, 6597683, 70046822, 623238099,183021267, 402682409, 631680428, 344509872, 689220186, 365017329, 774342554, 729444058, 102986190, 128751033, 395565204)irate3 = (509520358, 929031873, 170256584, 839780419, 282974284, 395914482, 444904435, 72135471, 638914820, 66769500,771127074, 985925487, 262319669, 262341272, 625870173, 768022760, 859816005, 914661783, 430819711, 272774365, 530924681)def butterfly(a):n = len(a)h = (n - 1).bit_length()len_ = 0while len_ < h:if h - len_ == 1:p = 1 << (h - len_ - 1)rot = 1for s in range(1 << len_):offset = s << (h - len_)for i in range(p):l = a[i + offset]r = a[i + offset + p] * rot % moda[i + offset] = (l + r) % moda[i + offset + p] = (l - r) % modif s + 1 != 1 << len_:rot *= rate2[(~s & -~s).bit_length() - 1]rot %= modlen_ += 1else:p = 1 << (h - len_ - 2)rot = 1for s in range(1 << len_):rot2 = rot * rot % modrot3 = rot2 * rot % modoffset = s << (h - len_)for i in range(p):a0 = a[i + offset]a1 = a[i + offset + p] * rota2 = a[i + offset + p * 2] * rot2a3 = a[i + offset + p * 3] * rot3a1na3imag = (a1 - a3) % mod * imaga[i + offset] = (a0 + a2 + a1 + a3) % moda[i + offset + p] = (a0 + a2 - a1 - a3) % moda[i + offset + p * 2] = (a0 - a2 + a1na3imag) % moda[i + offset + p * 3] = (a0 - a2 - a1na3imag) % modif s + 1 != 1 << len_:rot *= rate3[(~s & -~s).bit_length() - 1]rot %= modlen_ += 2def butterfly_inv(a):n = len(a)h = (n - 1).bit_length()len_ = hwhile len_:if len_ == 1:p = 1 << (h - len_)irot = 1for s in range(1 << (len_ - 1)):offset = s << (h - len_ + 1)for i in range(p):l = a[i + offset]r = a[i + offset + p]a[i + offset] = (l + r) % moda[i + offset + p] = (l - r) * irot % modif s + 1 != (1 << (len_ - 1)):irot *= irate2[(~s & -~s).bit_length() - 1]irot %= modlen_ -= 1else:p = 1 << (h - len_)irot = 1for s in range(1 << (len_ - 2)):irot2 = irot * irot % modirot3 = irot2 * irot % modoffset = s << (h - len_ + 2)for i in range(p):a0 = a[i + offset]a1 = a[i + offset + p]a2 = a[i + offset + p * 2]a3 = a[i + offset + p * 3]a2na3iimag = (a2 - a3) * iimag % moda[i + offset] = (a0 + a1 + a2 + a3) % moda[i + offset + p] = (a0 - a1 + a2na3iimag) * irot % moda[i + offset + p * 2] = (a0 + a1 - a2 - a3) * irot2 % moda[i + offset + p * 3] = (a0 - a1 - a2na3iimag) * irot3 % modif s + 1 != (1 << (len_ - 2)):irot *= irate3[(~s & -~s).bit_length() - 1]irot %= modlen_ -= 2def integrate(a):a=a.copy()n = len(a)assert n > 0a.pop()a.insert(0, 0)inv = [1, 1]for i in range(2, n):inv.append(-inv[mod%i] * (mod//i) % mod)a[i] = a[i] * inv[i] % modreturn adef differentiate(a):n = len(a)assert n > 0for i in range(2, n):a[i] = a[i] * i % moda.pop(0)a.append(0)return adef convolution_naive(a, b):n = len(a)m = len(b)ans = [0] * (n + m - 1)if n < m:for j in range(m):for i in range(n):ans[i + j] = (ans[i + j] + a[i] * b[j]) % modelse:for i in range(n):for j in range(m):ans[i + j] = (ans[i + j] + a[i] * b[j]) % modreturn ansdef convolution_ntt(a, b):a = a.copy()b = b.copy()n = len(a)m = len(b)z = 1 << (n + m - 2).bit_length()a += [0] * (z - n)butterfly(a)b += [0] * (z - m)butterfly(b)for i in range(z):a[i] = a[i] * b[i] % modbutterfly_inv(a)a = a[:n + m - 1]iz = pow(z, mod - 2, mod)for i in range(n + m - 1):a[i] = a[i] * iz % modreturn adef convolution_square(a):a = a.copy()n = len(a)z = 1 << (2 * n - 2).bit_length()a += [0] * (z - n)butterfly(a)for i in range(z):a[i] = a[i] * a[i] % modbutterfly_inv(a)a = a[:2 * n - 1]iz = pow(z, mod - 2, mod)for i in range(2 * n - 1):a[i] = a[i] * iz % modreturn adef convolution(a, b):"""It calculates (+, x) convolution in mod 998244353.Given two arrays a[0], a[1], ..., a[n - 1] and b[0], b[1], ..., b[m - 1],it calculates the array c of length n + m - 1, defined by> c[i] = sum(a[j] * b[i - j] for j in range(i + 1)) % 998244353.It returns an empty list if at least one of a and b are empty.Complexity----------> O(n log n), where n = len(a) + len(b)."""n = len(a)m = len(b)if n == 0 or m == 0:return []if min(n, m) <= 60:return convolution_naive(a, b)if a is b:return convolution_square(a)return convolution_ntt(a, b)def inverse(a):n = len(a)assert n > 0 and a[0] != 0res = [pow(a[0], mod - 2, mod)]m = 1while m < n:f = a[:min(n,2*m)] + [0]*(2*m-min(n,2*m))g = res + [0]*mbutterfly(f)butterfly(g)for i in range(2*m):f[i] = f[i] * g[i] % modbutterfly_inv(f)f = f[m:] + [0]*mbutterfly(f)for i in range(2*m):f[i] = f[i] * g[i] % modbutterfly_inv(f)iz = pow(2*m, mod-2, mod)iz = (-iz*iz) % modfor i in range(m):f[i] = f[i] * iz % modres += f[:m]m <<= 1return res[:n]def log(a):a = a.copy()n = len(a)assert n > 0 and a[0] == 1a_inv = inverse(a)a=differentiate(a)a = convolution(a, a_inv)[:n]a=integrate(a)return adef exp(a):a = a.copy()n = len(a)assert n > 0 and a[0] == 0g = [1]a[0] = 1h_drv = a.copy()h_drv=differentiate(h_drv)m = 1while m < n:f_fft = a[:m] + [0] * mbutterfly(f_fft)if m > 1:_f = [f_fft[i] * g_fft[i] % mod for i in range(m)]butterfly_inv(_f)_f = _f[m // 2:] + [0] * (m // 2)butterfly(_f)for i in range(m):_f[i] = _f[i] * g_fft[i] % modbutterfly_inv(_f)_f = _f[:m//2]iz = pow(m, mod - 2, mod)iz *= -iziz %= modfor i in range(m//2):_f[i] = _f[i] * iz % modg.extend(_f)t = a[:m]t=differentiate(t)r = h_drv[:m - 1]r.append(0)butterfly(r)for i in range(m):r[i] = r[i] * f_fft[i] % modbutterfly_inv(r)im = pow(-m, mod - 2, mod)for i in range(m):r[i] = r[i] * im % modfor i in range(m):t[i] = (t[i] + r[i]) % modt = [t[-1]] + t[:-1]t += [0] * mbutterfly(t)g_fft = g + [0] * (2 * m - len(g))butterfly(g_fft)for i in range(2 * m):t[i] = t[i] * g_fft[i] % modbutterfly_inv(t)t = t[:m]i2m = pow(2 * m, mod - 2, mod)for i in range(m):t[i] = t[i] * i2m % modv = a[m:min(n, 2 * m)]v += [0] * (m - len(v))t = [0] * (m - 1) + t + [0]t=integrate(t)for i in range(m):v[i] = (v[i] - t[m + i]) % modv += [0] * mbutterfly(v)for i in range(2 * m):v[i] = v[i] * f_fft[i] % modbutterfly_inv(v)v = v[:m]i2m = pow(2 * m, mod - 2, mod)for i in range(m):v[i] = v[i] * i2m % modfor i in range(min(n - m, m)):a[m + i] = v[i]m *= 2return adef power(a,k):n = len(a)assert n>0if k==0:return [1]+[0]*(n-1)l = 0while l < len(a) and not a[l]:l += 1if l * k >= n:return [0] * nic = pow(a[l], mod - 2, mod)pc = pow(a[l], k, mod)a = log([a[i] * ic % mod for i in range(l, len(a))])for i in range(len(a)):a[i] = a[i] * k % moda = exp(a)for i in range(len(a)):a[i] = a[i] * pc % moda = [0] * (l * k) + a[:n - l * k]return adef sqrt(a):if len(a) == 0:return []if a[0] == 0:for d in range(1, len(a)):if a[d]:if d & 1:return Noneif len(a) - 1 < d // 2:breakres=sqrt(a[d:]+[0]*(d//2))if res == None:return Noneres = [0]*(d//2)+resreturn resreturn [0]*len(a)sqr = Tonelli_Shanks(a[0],mod)if sqr == None:return NoneT = [0] * (len(a))T[0] = sqrres = T.copy()T[0] = pow(sqr,mod-2,mod) #T:res^{-1}m = 1two_inv = (mod + 1) // 2F = [sqr]while m <= len(a) - 1:for i in range(m):F[i] *= F[i]F[i] %= modbutterfly_inv(F)iz = pow(m, mod-2, mod)for i in range(m):F[i] = F[i] * iz % moddelta = [0] * (2 * m)for i in range(m):delta[i + m] = F[i] - a[i] - (a[i + m] if i+m<len(a) else 0)butterfly(delta)G = [0] * (2 * m)for i in range(m):G[i] = T[i]butterfly(G)for i in range(2 * m):delta[i] *= G[i]delta[i] %= modbutterfly_inv(delta)iz = pow(2*m, mod-2, mod)for i in range(2*m):delta[i] = delta[i] * iz % modfor i in range(m, min(2 * m, len(a))):res[i] = -delta[i] * two_inv%modres[i]%=modif 2 * m > len(a) - 1:breakF = res[:2 * m]butterfly(F)eps = [F[i] * G[i] % mod for i in range(2 * m)]butterfly_inv(eps)for i in range(m):eps[i] = 0iz = pow(2*m, mod-2, mod)for i in range(m,2*m):eps[i] = eps[i] * iz % modbutterfly(eps)for i in range(2 * m):eps[i] *= G[i]eps[i] %= modbutterfly_inv(eps)for i in range(m, 2 * m):T[i] = -eps[i]*izT[i]%=modiz = iz*iz % modm <<= 1return resdef Extended_Euclid(n,m):stack=[]while m:stack.append((n,m))n,m=m,n%mif n>=0:x,y=1,0else:x,y=-1,0for i in range(len(stack)-1,-1,-1):n,m=stack[i]x,y=y,x-(n//m)*yreturn x,yclass MOD:def __init__(self,p,e=None):self.p=pself.e=eif self.e==None:self.mod=self.pelse:self.mod=self.p**self.edef Pow(self,a,n):a%=self.modif n>=0:return pow(a,n,self.mod)else:#assert math.gcd(a,self.mod)==1x=Extended_Euclid(a,self.mod)[0]return pow(x,-n,self.mod)def Build_Fact(self,N):assert N>=0self.factorial=[1]if self.e==None:for i in range(1,N+1):self.factorial.append(self.factorial[-1]*i%self.mod)else:self.cnt=[0]*(N+1)for i in range(1,N+1):self.cnt[i]=self.cnt[i-1]ii=iwhile ii%self.p==0:ii//=self.pself.cnt[i]+=1self.factorial.append(self.factorial[-1]*ii%self.mod)self.factorial_inve=[None]*(N+1)self.factorial_inve[-1]=self.Pow(self.factorial[-1],-1)for i in range(N-1,-1,-1):ii=i+1while ii%self.p==0:ii//=self.pself.factorial_inve[i]=(self.factorial_inve[i+1]*ii)%self.moddef Build_Inverse(self,N):self.inverse=[None]*(N+1)assert self.p>Nself.inverse[1]=1for n in range(2,N+1):if n%self.p==0:continuea,b=divmod(self.mod,n)self.inverse[n]=(-a*self.inverse[b])%self.moddef Inverse(self,n):return self.inverse[n]def Fact(self,N):if N<0:return 0retu=self.factorial[N]if self.e!=None and self.cnt[N]:retu*=pow(self.p,self.cnt[N],self.mod)%self.modretu%=self.modreturn retudef Fact_Inve(self,N):if self.e!=None and self.cnt[N]:return Nonereturn self.factorial_inve[N]def Comb(self,N,K,divisible_count=False):if K<0 or K>N:return 0retu=self.factorial[N]*self.factorial_inve[K]%self.mod*self.factorial_inve[N-K]%self.modif self.e!=None:cnt=self.cnt[N]-self.cnt[N-K]-self.cnt[K]if divisible_count:return retu,cntelse:retu*=pow(self.p,cnt,self.mod)retu%=self.modreturn retuclass Polynomial:def __init__(self,polynomial,max_degree=-1,eps=0,mod=0):self.max_degree=max_degreeif self.max_degree!=-1 and len(polynomial)>self.max_degree+1:self.polynomial=polynomial[:self.max_degree+1]else:self.polynomial=polynomialself.mod=modself.eps=epsdef __eq__(self,other):if type(other)!=Polynomial:return Falseif len(self.polynomial)!=len(other.polynomial):return Falsefor i in range(len(self.polynomial)):if self.eps<abs(self.polynomial[i]-other.polynomial[i]):return Falsereturn Truedef __ne__(self,other):if type(other)!=Polynomial:return Trueif len(self.polynomial)!=len(other.polynomial):return Truefor i in range(len(self.polynomial)):if self.eps<abs(self.polynomial[i]-other.polynomial[i]):return Truereturn Falsedef __add__(self,other):if type(other)==Polynomial:summ=[0]*max(len(self.polynomial),len(other.polynomial))for i in range(len(self.polynomial)):summ[i]+=self.polynomial[i]for i in range(len(other.polynomial)):summ[i]+=other.polynomial[i]if self.mod:for i in range(len(summ)):summ[i]%=self.modelse:summ=[x for x in self.polynomial] if self.polynomial else [0]summ[0]+=otherif self.mod:summ[0]%=self.modwhile summ and abs(summ[-1])<=self.eps:summ.pop()summ=Polynomial(summ,max_degree=self.max_degree,eps=self.eps,mod=self.mod)return summdef __sub__(self,other):if type(other)==Polynomial:diff=[0]*max(len(self.polynomial),len(other.polynomial))for i in range(len(self.polynomial)):diff[i]+=self.polynomial[i]for i in range(len(other.polynomial)):diff[i]-=other.polynomial[i]if self.mod:for i in range(len(diff)):diff[i]%=self.modelse:diff=[x for x in self.polynomial] if self.polynomial else [0]diff[0]-=otherif self.mod:diff[0]%=self.modwhile diff and abs(diff[-1])<=self.eps:diff.pop()diff=Polynomial(diff,max_degree=self.max_degree,eps=self.eps,mod=self.mod)return diffdef __mul__(self,other):if type(other)==Polynomial:if self.max_degree==-1:prod=[0]*(len(self.polynomial)+len(other.polynomial)-1)for i in range(len(self.polynomial)):for j in range(len(other.polynomial)):prod[i+j]+=self.polynomial[i]*other.polynomial[j]else:prod=[0]*min(len(self.polynomial)+len(other.polynomial)-1,self.max_degree+1)for i in range(len(self.polynomial)):for j in range(min(len(other.polynomial),self.max_degree+1-i)):prod[i+j]+=self.polynomial[i]*other.polynomial[j]if self.mod:for i in range(len(prod)):prod[i]%=self.modelse:if self.mod:prod=[x*other%self.mod for x in self.polynomial]else:prod=[x*other for x in self.polynomial]while prod and abs(prod[-1])<=self.eps:prod.pop()prod=Polynomial(prod,max_degree=self.max_degree,eps=self.eps,mod=self.mod)return proddef __matmul__(self,other):assert type(other)==Polynomialif self.mod:prod=NTT(self.polynomial,other.polynomial)else:prod=FFT(self.polynomial,other.polynomial)if self.max_degree!=-1 and len(prod)>self.max_degree+1:prod=prod[:self.max_degree+1]while prod and abs(prod[-1])<=self.eps:prod.pop()prod=Polynomial(prod,max_degree=self.max_degree,eps=self.eps,mod=self.mod)return proddef __pow__(self,other):if other==0:prod=Polynomial([1],max_degree=self.max_degree,eps=self.eps,mod=self.mod)elif other==1:prod=Polynomial([x for x in self.polynomial],max_degree=self.max_degree,eps=self.eps,mod=self.mod)else:prod=[1]doub=self.polynomialif self.mod:convolve=NTTconvolve_Pow=NTT_Powelse:convolve=FFTconvolve_Pow=FFT_Powwhile other>=2:if other&1:prod=convolve(prod,doub)if self.max_degree!=-1:prod=prod[:self.max_degree+1]doub=convolve_Pow(doub,2)if self.max_degree!=-1:doub=doub[:self.max_degree+1]other>>=1prod=convolve(prod,doub)if self.max_degree!=-1:prod=prod[:self.max_degree+1]prod=Polynomial(prod,max_degree=self.max_degree,eps=self.eps,mod=self.mod)return proddef __truediv__(self,other):if type(other)==Polynomial:assert other.polynomialfor n in range(len(other.polynomial)):if self.eps<abs(other.polynomial[n]):breakassert len(self.polynomial)>nfor i in range(n):assert abs(self.polynomial[i])<=self.epsself_polynomial=self.polynomial[n:]other_polynomial=other.polynomial[n:]if self.mod:inve=MOD(self.mod).Pow(other_polynomial[0],-1)else:inve=1/other_polynomial[0]quot=[]for i in range(len(self_polynomial)-len(other_polynomial)+1):if self.mod:quot.append(self_polynomial[i]*inve%self.mod)else:quot.append(self_polynomial[i]*inve)for j in range(len(other_polynomial)):self_polynomial[i+j]-=other_polynomial[j]*quot[-1]if self.mod:self_polynomial[i+j]%=self.modfor i in range(max(0,len(self_polynomial)-len(other_polynomial)+1),len(self_polynomial)):if self.eps<abs(self_polynomial[i]):assert self.max_degree!=-1self_polynomial=self_polynomial[-len(other_polynomial)+1:]+[0]*(len(other_polynomial)-1-len(self_polynomial))while len(quot)<=self.max_degree:self_polynomial.append(0)if self.mod:quot.append(self_polynomial[0]*inve%self.mod)self_polynomial=[(self_polynomial[i]-other_polynomial[i]*quot[-1])%self.mod for i in range(1,len(self_polynomial))]else:quot.append(self_polynomial[0]*inve)self_polynomial=[(self_polynomial[i]-other_polynomial[i]*quot[-1]) for i in range(1,len(self_polynomial))]breakquot=Polynomial(quot,max_degree=self.max_degree,eps=self.eps,mod=self.mod)else:assert self.eps<abs(other)if self.mod:inve=MOD(self.mod).Pow(other,-1)quot=Polynomial([x*inve%self.mod for x in self.polynomial],max_degree=self.max_degree,eps=self.eps,mod=self.mod)else:quot=Polynomial([x/other for x in self.polynomial],max_degree=self.max_degree,eps=self.eps,mod=self.mod)return quotdef __floordiv__(self,other):assert type(other)==Polynomialquot=[0]*(len(self.polynomial)-len(other.polynomial)+1)rema=[x for x in self.polynomial]if self.mod:inve=MOD(self.mod).Pow(other.polynomial[-1],-1)for i in range(len(self.polynomial)-len(other.polynomial),-1,-1):quot[i]=rema[i+len(other.polynomial)-1]*inve%self.modfor j in range(len(other.polynomial)):rema[i+j]-=quot[i]*other.polynomial[j]rema[i+j]%=self.modelse:inve=1/other.polynomial[-1]for i in range(len(self.polynomial)-len(other.polynomial),-1,-1):quot[i]=rema[i+len(other.polynomial)-1]*invefor j in range(len(other.polynomial)):rema[i+j]-=quot[i]*other.polynomial[j]quot=Polynomial(quot,max_degree=self.max_degree,eps=self.eps,mod=self.mod)return quotdef __mod__(self,other):assert type(other)==Polynomialquot=[0]*(len(self.polynomial)-len(other.polynomial)+1)rema=[x for x in self.polynomial]if self.mod:inve=MOD(self.mod).Pow(other.polynomial[-1],-1)for i in range(len(self.polynomial)-len(other.polynomial),-1,-1):quot[i]=rema[i+len(other.polynomial)-1]*inve%self.modfor j in range(len(other.polynomial)):rema[i+j]-=quot[i]*other.polynomial[j]rema[i+j]%=self.modelse:inve=1/other.polynomial[-1]for i in range(len(self.polynomial)-len(other.polynomial),-1,-1):quot[i]=rema[i+len(other.polynomial)-1]*invefor j in range(len(other.polynomial)):rema[i+j]-=quot[i]*other.polynomial[j]while rema and abs(rema[-1])<=self.eps:rema.pop()rema=Polynomial(rema,max_degree=self.max_degree,eps=self.eps,mod=self.mod)return remadef __divmod__(self,other):assert type(other)==Polynomialquot=[0]*(len(self.polynomial)-len(other.polynomial)+1)rema=[x for x in self.polynomial]if self.mod:inve=MOD(self.mod).Pow(other.polynomial[-1],-1)for i in range(len(self.polynomial)-len(other.polynomial),-1,-1):quot[i]=rema[i+len(other.polynomial)-1]*inve%self.modfor j in range(len(other.polynomial)):rema[i+j]-=quot[i]*other.polynomial[j]rema[i+j]%=self.modelse:inve=1/other.polynomial[-1]for i in range(len(self.polynomial)-len(other.polynomial),-1,-1):quot[i]=rema[i+len(other.polynomial)-1]*invefor j in range(len(other.polynomial)):rema[i+j]-=quot[i]*other.polynomial[j]while rema and abs(rema[-1])<=self.eps:rema.pop()quot=Polynomial(quot,max_degree=self.max_degree,eps=self.eps,mod=self.mod)rema=Polynomial(rema,max_degree=self.max_degree,eps=self.eps,mod=self.mod)return quot,remadef __neg__(self):if self.mod:nega=Polynomial([(-x)%self.mod for x in self.polynomial],max_degree=self.max_degree,eps=self.eps,mod=self.mod)else:nega=Polynomial([-x for x in self.polynomial],max_degree=self.max_degree,eps=self.eps,mod=self.mod)return negadef __pos__(self):posi=Polynomial([x for x in self.polynomial],max_degree=self.max_degree,eps=self.eps,mod=self.mod)return posidef __bool__(self):return self.polynomialdef __getitem__(self,n):if type(n)==int:if n<=len(self.polynomial)-1:return self.polynomial[n]else:return 0else:return Polynomial(polynomial=self.polynomial[n],max_degree=self.max_degree,eps=self.eps,mod=self.mod)def __setitem__(self,n,a):if self.mod:a%=self.modif self.max_degree==-1 or n<=self.max_degree:if n<=len(self.polynomial)-1:self.polynomial[n]=aelif self.eps<abs(a):self.polynomial+=[0]*(n-len(self.polynomial))+[a]def __iter__(self):for x in self.polynomial:yield xdef __call__(self,x):retu=0pow_x=1for i in range(len(self.polynomial)):retu+=pow_x*self.polynomial[i]pow_x*=xif self.mod:retu%=self.modpow_x%=self.modreturn retudef __str__(self):return "["+", ".join(map(str,self.polynomial))+"]"def __len__(self):return len(self.polynomial)def differentiate(self):if self.mod:differential=[x*i%self.mod for i,x in enumerate(self.polynomial[1:],1)]else:differential=[x*i for i,x in enumerate(self.polynomial[1:],1)]return Polynomial(differential,max_degree=self.max_degree,eps=self.eps,mod=self.mod)def integrate(self):if self.mod:integral=[0]+[x*MOD(mod).Pow(i+1,-1)%self.mod for i,x in enumerate(self.polynomial)]else:integral=[0]+[x/(i+1) for i,x in enumerate(self.polynomial)]while integral and abs(integral[-1])<=self.eps:integral.pop()return Polynomial(integral,max_degree=self.max_degree,eps=self.eps,mod=self.mod)def inverse(self):assert self.polynomial and self.eps<self.polynomial[0]assert self.max_degree!=-1if self.mod:quot=[MOD(self.mod).Pow(self.polynomial[0],-1)]if self.mod==998244353:prim_root=3prim_root_inve=332748118else:prim_root=Primitive_Root(self.mod)prim_root_inve=MOD(self.mod).Pow(prim_root,-1)def DFT(polynomial,n,inverse=False):polynomial=polynomial+[0]*((1<<n)-len(polynomial))if inverse:for bit in range(1,n+1):a=1<<bit-1x=pow(prim_root,self.mod-1>>bit,self.mod)U=[1]for _ in range(a):U.append(U[-1]*x%self.mod)for i in range(1<<n-bit):for j in range(a):s=i*2*a+jt=s+apolynomial[s],polynomial[t]=(polynomial[s]+polynomial[t]*U[j])%self.mod,(polynomial[s]-polynomial[t]*U[j])%self.modx=pow((self.mod+1)//2,n,self.mod)for i in range(1<<n):polynomial[i]*=xpolynomial[i]%=self.modelse:for bit in range(n,0,-1):a=1<<bit-1x=pow(prim_root_inve,self.mod-1>>bit,self.mod)U=[1]for _ in range(a):U.append(U[-1]*x%self.mod)for i in range(1<<n-bit):for j in range(a):s=i*2*a+jt=s+apolynomial[s],polynomial[t]=(polynomial[s]+polynomial[t])%self.mod,U[j]*(polynomial[s]-polynomial[t])%self.modreturn polynomialelse:quot=[1/self.polynomial[0]]def DFT(polynomial,n,inverse=False):N=len(polynomial)if inverse:primitive_root=[math.cos(-i*2*math.pi/(1<<n))+math.sin(-i*2*math.pi/(1<<n))*1j for i in range(1<<n)]else:primitive_root=[math.cos(i*2*math.pi/(1<<n))+math.sin(i*2*math.pi/(1<<n))*1j for i in range(1<<n)]polynomial=polynomial+[0]*((1<<n)-N)if inverse:for bit in range(1,n+1):a=1<<bit-1for i in range(1<<n-bit):for j in range(a):s=i*2*a+jt=s+apolynomial[s],polynomial[t]=polynomial[s]+polynomial[t]*primitive_root[j<<n-bit],polynomial[s]-polynomial[t]*primitive_root[j<<n-bit]for i in range(1<<n):polynomial[i]=round((polynomial[i]/(1<<n)).real)else:for bit in range(n,0,-1):a=1<<bit-1for i in range(1<<n-bit):for j in range(a):s=i*2*a+jt=s+apolynomial[s],polynomial[t]=polynomial[s]+polynomial[t],primitive_root[j<<n-bit]*(polynomial[s]-polynomial[t])return polynomialfor n in range(self.max_degree.bit_length()):prev=quotDFT_prev=DFT(prev,n+1)if self.mod:quot=[x*y%self.mod for x,y in zip(DFT_prev,DFT(self.polynomial[:1<<n+1],n+1))]else:quot=[x*y for x,y in zip(DFT_prev,DFT(self.polynomial[:1<<n+1],n+1))]quot=DFT([0]*(1<<n)+DFT(quot,n+1,inverse=True)[1<<n:],n+1)if self.mod:quot=[(-x*y)%self.mod for x,y in zip(DFT_prev,quot)]else:quot=[-x*y for x,y in zip(DFT_prev,quot)]quot=prev+DFT(quot,n+1,inverse=True)[1<<n:]quot=quot[:self.max_degree+1]quot=Polynomial(quot,max_degree=self.max_degree,eps=self.eps,mod=self.mod)return quotdef log(self):assert self.max_degree!=-1assert self.polynomial and abs(self.polynomial[0]-1)<=self.epslog=self.inverse()if self.mod:log=Polynomial(NTT(self.differentiate().polynomial,log.polynomial),max_degree=self.max_degree,eps=self.eps,mod=self.mod)else:log=Polynomial(FFT(self.differentiate().polynomial,log.polynomial),max_degree=self.max_degree,eps=self.eps,mod=self.mod)log=log.integrate()return logdef Newton(self,n0,f,differentiated_f=None):newton=[n0]while len(newton)<self.max_degree+1:prev=newtonif differentiated_f==None:newton=f(prev,self.polynomial)else:newton=f(prev)for i in range(min(len(self.polynomial),len(newton))):newton[i]-=self.polynomial[i]newton[i]%=self.modif self.mod:newton=NTT(newton,Polynomial(differentiated_f(prev),max_degree=len(newton)-1,eps=self.eps,mod=self.mod).inverse().polynomial)[:len(newton)]else:newton=FFT(newton,Polynomial(differentiated_f(prev),max_degree=len(newton)-1,eps=self.eps,mod=self.mod).inverse().polynomial)[:len(newton)]for i in range(len(newton)):newton[i]=-newton[i]newton[i]%=self.modfor i in range(len(prev)):newton[i]+=prev[i]newton[i]%=self.modnewton=newton[:self.max_degree+1]while newton and newton[-1]<=self.eps:newton.pop()return Polynomial(newton,max_degree=self.max_degree,eps=self.eps,mod=self.mod)def sqrt(self):if self.polynomial:for cnt0 in range(len(self.polynomial)):if self.polynomial[cnt0]:breakif cnt0%2:sqrt=Noneelse:if self.mod:n0=Tonelli_Shanks(self.polynomial[cnt0],self.mod)else:if self.polynomial[cnt0]>=self.eps:n0=self.polynomial[cnt0]**.5if n0==None:sqrt=Noneelse:def f(prev):if self.mod:return NTT_Pow(prev,2)+[0]else:return FFT_Pow(prev,2)+[0]def differentiated_f(prev):retu=[0]*(2*len(prev)-1)for i in range(len(prev)):retu[i]+=2*prev[i]if self.mod:retu[i]%self.modreturn retusqrt=[0]*(cnt0//2)+Polynomial(self.polynomial[cnt0:],max_degree=self.max_degree-cnt0//2,mod=self.mod).Newton(n0,f,differentiated_f).polynomialsqrt=Polynomial(sqrt,max_degree=self.max_degree,eps=self.eps,mod=self.mod)else:sqrt=Polynomial([],max_degree=self.max_degree,eps=self.eps,mod=self.mod)return sqrtdef exp(self):assert not self.polynomial or abs(self.polynomial[0])<=self.epsdef f(prev,poly):newton=Polynomial(prev,max_degree=2*len(prev)-1,eps=self.eps,mod=self.mod).log().polynomialnewton+=[0]*(2*len(prev)-len(newton))for i in range(min(len(poly),len(newton))):newton[i]-=poly[i]if self.mod:for i in range(len(newton)):newton[i]%=self.modif self.mod:return NTT(prev,newton)[:2*len(prev)]else:return FFT(prev,newton)[:2*len(prev)]return Polynomial(self.polynomial,max_degree=self.max_degree,mod=self.mod).Newton(1,f)def Degree(self):return len(self.polynomial)-1def Hadamard(polynomial,n,mod=0,inverse=False):polynomial_=[x for x in polynomial]+[0]*((1<<n)-len(polynomial))for bit in range(n):for i in range(1<<n):ii=i^(1<<bit)if i>ii:continuepolynomial_[i],polynomial_[ii]=polynomial_[i]+polynomial_[ii],polynomial_[i]-polynomial_[ii]if mod:polynomial_[i]%=modpolynomial_[ii]%=modif inverse:if mod:inve_2=pow((mod+1)//2,n)for i in range(1<<n):polynomial_[i]*=inve_2polynomial_[i]%=modelse:pow_2=pow(2,n)for i in range(1<<n):polynomial_[i]/=pow_2return polynomial_def XOR_Convolution(polynomial0,polynomial1,mod=0):n=(max(len(polynomial0),len(polynomial1))-1).bit_length()Hadamard_polynomial0=Hadamard(polynomial0,n,mod=mod)Hadamard_polynomial1=Hadamard(polynomial1,n,mod=mod)if mod:convolution=[x*y%mod for x,y in zip(Hadamard_polynomial0,Hadamard_polynomial1)]else:convolution=[x*y for x,y in zip(Hadamard_polynomial0,Hadamard_polynomial1)]convolution=Hadamard(convolution,n,mod=mod,inverse=True)return convolutiondef Bostan_Mori(poly_nume,poly_deno,N,mod=0,convolve=None):if type(poly_nume)==Polynomial:poly_nume=poly_nume.polynomialif type(poly_deno)==Polynomial:poly_deno=poly_deno.polynomialif convolve==None:def convolve(poly_nume,poly_deno):conv=[0]*(len(poly_nume)+len(poly_deno)-1)for i in range(len(poly_nume)):for j in range(len(poly_deno)):x=poly_nume[i]*poly_deno[j]if mod:x%=modconv[i+j]+=xif mod:for i in range(len(conv)):conv[i]%=modreturn convwhile N:poly_deno_=[-x if i%2 else x for i,x in enumerate(poly_deno)]if N%2:poly_nume=convolve(poly_nume,poly_deno_)[1::2]else:poly_nume=convolve(poly_nume,poly_deno_)[::2]poly_deno=convolve(poly_deno,poly_deno_)[::2]if mod:for i in range(len(poly_nume)):poly_nume[i]%=modfor i in range(len(poly_deno)):poly_deno[i]%=modN//=2return poly_nume[0]from itertools import zip_longestN,M=map(int,readline().split())if M==1:ans=0else:mod=998244353nume,deno=[],[1]for m in range(2,M+1):nu,de=[1]*m,[1]*(m+1)nu[0]=0de[m]=-1nume=[(x+y)%mod for x,y in zip_longest(convolution(nume,de),convolution(nu,deno),fillvalue=0)]deno=convolution(deno,de)nume,deno=deno,[(d-n)%mod for d,n in zip_longest(deno,nume,fillvalue=0)]ans=Bostan_Mori(nume,deno,N,mod,convolve=convolution)print(ans)