from collections import deque MOD = 998244353 class FFT: inv_ = [1] def __init__(self, MOD=998244353): FFT.MOD = MOD g = self.primitive_root_constexpr() ig = pow(g, FFT.MOD - 2, FFT.MOD) FFT.W = [pow(g, (FFT.MOD - 1) >> i, FFT.MOD) for i in range(30)] FFT.iW = [pow(ig, (FFT.MOD - 1) >> i, FFT.MOD) for i in range(30)] def primitive_root_constexpr(self): if FFT.MOD == 998244353: return 3 elif FFT.MOD == 200003: return 2 elif FFT.MOD == 167772161: return 3 elif FFT.MOD == 469762049: return 3 elif FFT.MOD == 754974721: return 11 divs = [0] * 20 divs[0] = 2 cnt = 1 x = (FFT.MOD - 1) // 2 while x % 2 == 0: x //= 2 i = 3 while i * i <= x: if x % i == 0: divs[cnt] = i cnt += 1 while x % i == 0: x //= i i += 2 if x > 1: divs[cnt] = x cnt += 1 g = 2 while 1: ok = True for i in range(cnt): if pow(g, (FFT.MOD - 1) // divs[i], FFT.MOD) == 1: ok = False break if ok: return g g += 1 def fft(self, k, f): for l in range(k, 0, -1): d = 1 << l - 1 U = [1] for i in range(d): U.append(U[-1] * FFT.W[l] % FFT.MOD) for i in range(1 << k - l): for j in range(d): s = i * 2 * d + j f[s], f[s + d] = (f[s] + f[s + d]) % FFT.MOD, U[j] * (f[s] - f[s + d]) % FFT.MOD def ifft(self, k, f): for l in range(1, k + 1): d = 1 << l - 1 for i in range(1 << k - l): u = 1 for j in range(i * 2 * d, (i * 2 + 1) * d): f[j+d] *= u f[j], f[j + d] = (f[j] + f[j + d]) % FFT.MOD, (f[j] - f[j + d]) % FFT.MOD u = u * FFT.iW[l] % FFT.MOD def convolve(self, A, B): n0 = len(A) + len(B) - 1 k = (n0).bit_length() n = 1 << k A += [0] * (n - len(A)) B += [0] * (n - len(B)) self.fft(k, A) self.fft(k, B) A = [a * b % FFT.MOD for a, b in zip(A, B)] self.ifft(k, A) inv = pow(n, FFT.MOD - 2, FFT.MOD) A = [a * inv % FFT.MOD for a in A] del A[n0:] return A # [x ^ n] P(x) / Q(x) def BostanMori(P, Q, n): fft = FFT() while n: R = [(x * (-1) ** (i % 2)) % MOD for i, x in enumerate(Q)] Q = fft.convolve(Q, R[:])[::2] P = fft.convolve(P, R[:])[n % 2::2] n >>= 1 return P[0] * pow(Q[0], MOD - 2, MOD) % MOD n, m = map(int, input().split()) if m == 1: print(0) exit() queue = deque() fft = FFT() for i in range(2, m + 1): q = [1] * (i + 1) q[i] = -1 p = [1] * i p[0] = 0 queue.append((p, q)) while len(queue) >= 2: p1, q1 = queue.popleft() p2, q2 = queue.popleft() l1 = len(q1) l2 = len(q2) nq = fft.convolve(q1[:], q2[:]) np1 = fft.convolve(p1, q2) np2 = fft.convolve(p2, q1) assert len(np1) == len(np2) np = [(p1 + p2) % MOD for p1, p2 in zip(np1, np2)] queue.append((np, nq)) P, Q = queue.popleft() Q_P = Q[:] + [0] * (len(P) - len(Q)) for i, p in enumerate(P): Q_P[i] -= p Q_P[i] %= MOD ans = BostanMori(Q, Q_P, n) print(ans) """ (1 + x - x^2) / (1 - x^2) (1 + x - x^2) / (2 + x - 2x^2) (1 + x + x^2 - x^3) / (1 - x^3) (1 + x + x^2 - x^3) / (2 + x + x^2 - 2x^2) """