#include <bits/stdc++.h>
template <class T>
inline void readInt(T &w) {
char c, p = 0;
while (!isdigit(c = getchar())) p = c == '-';
for (w = c & 15; isdigit(c = getchar());) w = w * 10 + (c & 15);
if (p) w = -w;
}
constexpr int P(998244353), G(3);
inline int fpow(int x, int k = P - 2) {
int r = 1;
for (; k; k >>= 1, x = 1LL * x * x % P)
if (k & 1) r = 1LL * r * x % P;
return r;
}
namespace Polynomial {
int omega[1 << 21 | 5];
void init(int n) {
// static int now = 1;
// omega[1] = 1;
// while (now < n) {
// now <<= 1;
// int base = fpow(G, (P - 1) / now);
// for (int i = now; i < (now << 1); i++)
// omega[i] = i & 1 ? 1LL * omega[i - 1] * base % P : omega[i >> 1];
// }
}
inline int *alloc(int n) {
static int mem_pool[1 << 24 | 5], *ptr = mem_pool;
return ptr += n, ptr - n;
}
struct Polynomial {
int n, *a;
Polynomial(int n, int *a): n(n), a(a) {}
Polynomial(int n): n(n) { a = alloc(n); }
inline int &operator[](const int &i) { return a[i]; }
inline const int &operator[](const int &i) const { return a[i]; }
void dft() {
for (int k = n >> 1; k; k >>= 1) {
omega[0] = 1;
int base = fpow(G, (P - 1) / (k << 1));
for (int i = 1; i < k; i++) omega[i] = 1LL * omega[i - 1] * base % P;
for (int i = 0; i < n; i += k << 1) {
int *p = a + i, *q = p + k, *w = omega;
for (int j = 0; j < k; j++, p++, q++, w++) {
int t = *q;
*q = (1LL * *p - t + P) * *w % P, *p += t;
if (*p >= P) *p -= P;
}
}
}
}
void idft() {
for (int k = 1; k < n; k <<= 1) {
omega[0] = 1;
int base = fpow(G, (P - 1) / (k << 1));
for (int i = 1; i < k; i++) omega[i] = 1LL * omega[i - 1] * base % P;
for (int i = 0; i < n; i += k << 1) {
int *p = a + i, *q = p + k, *w = omega;
for (int j = 0; j < k; j++, p++, q++, w++) {
int t = 1LL * *q * *w % P;
*q = *p - t, *p += t;
if (*q < 0) *q += P;
if (*p >= P) *p -= P;
}
}
}
int inv = fpow(n);
for (int i = 0; i < n; i++) a[i] = 1LL * a[i] * inv % P;
std::reverse(a + 1, a + n);
}
};
} // namespace Polynomial
void poly_multiply(unsigned *A, int n, unsigned *B, int m, unsigned *C) {
int k = 1 << std::__lg(n + m) + 1;
Polynomial::Polynomial a(k), b(k), c(k);
for (int i = 0; i <= n; i++) a[i] = A[i];
for (int i = 0; i <= m; i++) b[i] = B[i];
Polynomial::init(k);
a.dft(), b.dft();
for (int i = 0; i < k; i++) c[i] = 1LL * a[i] * b[i] % P;
c.idft();
for (int i = 0; i <= n + m; i++) C[i] = c[i];
}