結果
問題 | No.2959 Dolls' Tea Party |
ユーザー |
![]() |
提出日時 | 2024-11-09 02:05:15 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,932 ms / 3,000 ms |
コード長 | 24,711 bytes |
コンパイル時間 | 384 ms |
コンパイル使用メモリ | 82,892 KB |
実行使用メモリ | 172,472 KB |
最終ジャッジ日時 | 2024-11-09 02:06:43 |
合計ジャッジ時間 | 79,742 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 33 |
ソースコード
import mathfrom functools import lru_cache#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 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 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 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 division_modulus(f,g):n=len(f)m=len(g)while m and g[m-1]==0:m-=1assert mif n>=m:fR=f[::-1][:n-m+1]gR=g[:m][::-1][:n-m+1]+[0]*max(0,n-m+1-m)qR=convolution(fR,inverse(gR))[:n-m+1]q=qR[::-1]r=[(f[i]-x)%mod for i,x in enumerate(convolution(g,q)[:m-1])]while r and r[-1]==0:r.pop()else:q,r=[],f.copy()return q,rdef taylor_shift(a,c):a=a.copy()n=len(a)#MD=MOD(mod)#MD.Build_Fact(n-1)for i in range(n):a[i]*=MD.Fact(i)a[i]%=modC=[1]for i in range(1,n):C.append(C[-1]*c%mod)for i in range(n):C[i]*=MD.Fact_Inve(i)C[i]%=moda=convolution(a,C[::-1])[n-1:]for i in range(n):a[i]*=MD.Fact_Inve(i)a[i]%=modreturn adef multipoint_evaluation(f, x):n = len(x)sz = 1 << (n - 1).bit_length()g = [[1] for _ in range(2 * sz)]for i in range(n):g[i + sz] = [-x[i], 1]for i in range(1, sz)[::-1]:g[i] = convolution(g[2 * i],g[2 * i + 1])g[1] =division_modulus(f,g[1])[1]for i in range(2, 2 * sz):g[i]=division_modulus(g[i>>1],g[i])[1]res = [g[i + sz][0] if g[i+sz] else 0 for i in range(n)]return resdef Chirp_Z_transform(f,q,M):if q==0:if f:return f[0]%modelse:return 0if M==0:return []N=len(f)pow_q=[1]+[q]*(N+M-2)inve_q=pow(q,mod-2,mod)pow_inve_q=[1]+[inve_q]*(N+M-2)for _ in range(2):for i in range(1,N+M-1):pow_q[i]*=pow_q[i-1]pow_q[i]%=modpow_inve_q[i]*=pow_inve_q[i-1]pow_inve_q[i]%=moda=[f[i]*pow_inve_q[i]%mod for i in range(N-1,-1,-1)]b=pow_qab=convolution(a,b)return [ab[j+N-1]*pow_inve_q[j]%mod for j in range(M)]def relaxed_convolution(N,f):retu=[0]*NA,B=[],[]C=Nonefor i in range(N):a,b=f(i,C)A.append(a)B.append(b)pow2=1while (i+2)%pow2==0:if pow2==i+2:breakelif pow2*2==i+2:tpl=((i+1-pow2,i+1,i+1-pow2,i+1),)else:tpl=((pow2-1,2*pow2-1,i+1-pow2,i+1),(i+1-pow2,i+1,pow2-1,2*pow2-1),)for la,ra,lb,rb in tpl:for j,c in enumerate(convolution(A[la:ra],B[lb:rb]),la+lb):if j<N:retu[j]+=cretu[j]%=modpow2*=2C=retu[i]return retudef Berlekamp_Massey(A,mod):n = len(A)B, C = [1], [1]l, m, p = 0, 1, 1for i in range(n):d = A[i]for j in range(1, l + 1):d += C[j] * A[i - j]d %= modif d == 0:m += 1continueT = C.copy()q = pow(p, mod - 2, mod) * d % modif len(C) < len(B) + m:C += [0] * (len(B) + m - len(C))for j, b in enumerate(B):C[j + m] -= q * bC[j + m] %= modif 2 * l <= i:B = Tl, m, p = i + 1 - l, 1, delse:m += 1res = [-c % mod for c in C[1:]]return resdef BMBM(A,N,mod):deno=[1]+[-c for c in Berlekamp_Massey(A,mod)]nume=[0]*(len(deno)-1)for i in range(len(A)):for j in range(len(deno)):if i+j<len(nume):nume[i+j]+=A[i]*deno[j]nume[i+j]%=modreturn Bostan_Mori(nume,deno,N,mod=mod)import mathfrom collections import defaultdict# pow/log/exp of FPS# thanks for https://judge.yosupo.jp/submission/126665# FFT# code from: https://atcoder.jp/contests/practice2/submissions/24974537# but changed a little_fft_mod = 998244353_fft_imag = 911660635_fft_iimag = 86583718_fft_rate2 = (911660635, 509520358, 369330050, 332049552, 983190778, 123842337, 238493703, 975955924, 603855026, 856644456, 131300601, 842657263,730768835, 942482514, 806263778, 151565301, 510815449, 503497456, 743006876, 741047443, 56250497, 867605899)_fft_irate2 = (86583718, 372528824, 373294451, 645684063, 112220581, 692852209, 155456985, 797128860, 90816748, 860285882, 927414960, 354738543,109331171, 293255632, 535113200, 308540755, 121186627, 608385704, 438932459, 359477183, 824071951, 103369235)_fft_rate3 = (372528824, 337190230, 454590761, 816400692, 578227951, 180142363, 83780245, 6597683, 70046822, 623238099, 183021267, 402682409,631680428, 344509872, 689220186, 365017329, 774342554, 729444058, 102986190, 128751033, 395565204)_fft_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 % _fft_moda[i + offset] = (l + r) % _fft_moda[i + offset + p] = (l - r) % _fft_modif s + 1 != (1 << len_):rot *= _fft_rate2[(~s & -~s).bit_length() - 1]rot %= _fft_modlen_ += 1else:p = 1 << (h - len_ - 2)rot = 1for s in range(1 << len_):rot2 = rot * rot % _fft_modrot3 = rot2 * rot % _fft_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) % _fft_mod * _fft_imaga[i + offset] = (a0 + a2 + a1 + a3) % _fft_moda[i + offset + p] = (a0 + a2 - a1 - a3) % _fft_moda[i + offset + p * 2] = (a0 - a2 + a1na3imag) % _fft_moda[i + offset + p * 3] = (a0 - a2 - a1na3imag) % _fft_modif s + 1 != (1 << len_):rot *= _fft_rate3[(~s & -~s).bit_length() - 1]rot %= _fft_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) % _fft_moda[i + offset + p] = (l - r) * irot % _fft_modif s + 1 != (1 << (len_ - 1)):irot *= _fft_irate2[(~s & -~s).bit_length() - 1]irot %= _fft_modlen_ -= 1else:p = 1 << (h - len_)irot = 1for s in range(1 << (len_ - 2)):irot2 = irot * irot % _fft_modirot3 = irot2 * irot % _fft_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) * _fft_iimag % _fft_moda[i + offset] = (a0 + a1 + a2 + a3) % _fft_moda[i + offset + p] = (a0 - a1 +a2na3iimag) * irot % _fft_moda[i + offset + p * 2] = (a0 + a1 -a2 - a3) * irot2 % _fft_moda[i + offset + p * 3] = (a0 - a1 -a2na3iimag) * irot3 % _fft_modif s + 1 != (1 << (len_ - 1)):irot *= _fft_irate3[(~s & -~s).bit_length() - 1]irot %= _fft_modlen_ -= 2def _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]) % _fft_modelse:for i in range(n):for j in range(m):ans[i + j] = (ans[i + j] + a[i] * b[j]) % _fft_modreturn ansdef _convolution_fft(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] % _fft_mod_butterfly_inv(a)a = a[:n + m - 1]iz = pow(z, _fft_mod - 2, _fft_mod)for i in range(n + m - 1):a[i] = a[i] * iz % _fft_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] % _fft_mod_butterfly_inv(a)a = a[:2 * n - 1]iz = pow(z, _fft_mod - 2, _fft_mod)for i in range(2 * n - 1):a[i] = a[i] * iz % _fft_modreturn adef convolution(a, b):n = len(a)m = len(b)if n == 0 or m == 0:return []if min(n, m) <= 0:return _convolution_naive(a, b)if a is b:return _convolution_square(a)return _convolution_fft(a, b)# ----# 1/F# 必要 : a[0] != 0# 前提 : FFTdef poly_inv(a, length = None):if length == None: M = len(a)else: M = lengthif M <= 0: return []n = len(a)r = pow(a[0], _fft_mod-2, _fft_mod)m = 1res = [r]while m < M:f = a[:min(n,2*m)] + [0]*(2*m-min(n,2*m))g = res + [0]*m_butterfly(f)_butterfly(g)for i in range(2*m):f[i] = f[i] * g[i] % _fft_mod_butterfly_inv(f)f = f[m:] + [0]*m_butterfly(f)for i in range(2*m):f[i] = f[i] * g[i] % _fft_mod_butterfly_inv(f)iz = pow(2*m, _fft_mod-2, _fft_mod)iz = (-iz*iz) % _fft_modfor i in range(m):f[i] = f[i] * iz % _fft_modres += f[:m]m <<= 1return res[:M]# 多点評価# x に評価したい点を配列で入れよう!def multi_eval(x, a):n = len(x)siz = 1 << (n-1).bit_length()g = [[1] for i in range(2 * siz)]for i in range(n):g[i + siz] = [-x[i], 1]for i in range(siz-1, 0, -1):g[i] = convolution(g[2 * i], g[2 * i + 1])for i in range(1, 2 * siz):if i == 1: f = a[::]else: f = g[i >> 1]m = len(f) - len(g[i]) + 1v = convolution(f[::-1][:m], poly_inv(g[i][::-1], m))[m-1::-1]w = convolution(v, g[i])g[i] = f[::]h = g[i]for j in range(len(w)):h[j] -= w[j]h[j] %= _fft_modwhile len(h) > 1 and h[-1] == 0:h.pop()return [g[i+siz][0] for i in range(n)]# DEF MOD FACTmod = _fft_modN = 10**6 + 5fact = [1]*(N+1)factinv = [1]*(N+1)for i in range(2, N+1):fact[i] = fact[i-1] * i % modfactinv[-1] = pow(fact[-1], mod-2, mod)for i in range(N-1, 1, -1):factinv[i] = factinv[i+1] * (i+1) % moddef cmb(a, b):if (a < b) or (b < 0): return 0return fact[a] * factinv[b] % mod * factinv[a-b] % mod# log(F)# 必要 : a[0] = 1# 前提 : FFT, invdef poly_log(a, length = None):if length == None: M = len(a)else: M = lengthif M <= 0: return []n = len(a)if n == 1: return [0] * Mb = [a[i+1] * (i+1) % _fft_mod for i in range(n-1)]t = convolution(b, poly_inv(a, length = M))return [0] + [t[i] * factinv[i+1] % _fft_mod * fact[i] % _fft_mod for i in range(M-1)]# exp(F)# 必要 : a[0] = 0# 前提 : FFT, inv, logdef poly_exp(a, length = None):if length == None: M = len(a)else: M = lengthif M <= 0: return []n = len(a)m = 1res = [1]while m < M:f = a[:min(n,2*m)] + [0]*(2*m-min(n,2*m))#print(res)v = poly_log(res, length = 2*m)w = [(f[i]-v[i])%_fft_mod for i in range(2*m)]w[0] = (w[0]+1)%_fft_modg = convolution(res, w)res += g[m:2*m]m <<= 1return res[:M]def poly_pow_nonzero(a, m, l):n = len(a)bais = pow(a[0], m, _fft_mod)invs = pow(a[0], _fft_mod-2, _fft_mod)r = [a[i] * invs % _fft_mod for i in range(n)]r = poly_log(r, length = l)for i in range(l):r[i] = r[i] * m % _fft_modr = poly_exp(r, length = l)for i in range(l):r[i] = r[i] * bais % _fft_modreturn rdef poly_pow(a, m, l):n = len(a)ind = 0for i in range(n):if a[i] != 0:ind = ibreakif ind * m >= l:return [0] * lreturn [0] * (ind * m) + poly_pow_nonzero(a[ind:], m, l-ind*m)# DEF MOD FACT はされています!!6def main():N,K=map(int,input().split())A=list(map(int,input().split()))mod=998244353MOD=998244353facts = [1] * (K + 1)ifacts = [1] * (K + 1)for i in range(K):facts[i + 1] = facts[i] * (i + 1) % MODifacts[i + 1] = pow(facts[i + 1], MOD - 2, MOD)F = [[0 for i in range(K + 1)] for j in range(K + 1)]F_log = [[0 for i in range(K + 1)] for j in range(K + 1)]for i in range(K + 1):for j in range(i + 1):F[i][j] = ifacts[j]F_log[i] = poly_log(F[i])memo_log=F_logans=0cntD=[0]*(K+1)for d in range(K):cntD[math.gcd(K,d)]+=1for d in range(K+1):if cntD[d]:S=K//dcnt=[0]*(d+2)for i in range(N):cnt[min(d,A[i]//S)]+=1poly=exp([sum(memo_log[c][x]*cnt[c]%mod for c in range(1,d+1)) for x in range(d+1)])ans+=cntD[d]*poly[d]%mod*fact[d]%modans%=modans*=pow(K,mod-2,mod)ans%=modprint(ans)main()