#include <math.h>
#include <string.h>
typedef long long ll;
#define N 2100005
#define M 8400005
#define G 25
const int P = 998244353, g = 3;
int fxt (int x) { int l = 1; while (l <= x) l <<= 1; return l; }
int fpow (int a, int t) {
static int r;
for (r = 1; t; t >>= 1, a = (ll)a * a % P) if (t & 1) r = (ll)r * a % P;
return r;
}
int pol[M], *ed = pol, inv[N], fac[N], ifac[N], *ww[G], *iww[G], *_w;
int *nint (int len) { int *r = ed; ed += len; return r; }
void init (int n) {
int i, j, k, w, iw;
for (i = j = 1; j <= n; i ++, j <<= 1) {
ww[i] = nint(j), iww[i] = nint(j), ww[i][0] = iww[i][0] = 1;
w = fpow(g, (P - 1) >> i), iw = fpow(w, P - 2);
for (k = 1; k < j; k ++) ww[i][k] = (ll)ww[i][k - 1] * w % P, iww[i][k] = (ll)iww[i][k - 1] * iw % P;
}
inv[1] = 1;
for (i = 2; i <= n; i ++) inv[i] = P - (ll)inv[P % i] * (P / i) % P;
fac[0] = ifac[0] = 1;
for (i = 1; i <= n; i ++) fac[i] = (ll)fac[i - 1] * i % P, ifac[i] = (ll)ifac[i - 1] * inv[i] % P;
}
void fft (int a[], int n, int dft) {
int i, j, k, l, c = 0, u, v;
for (i = 1, j = n >> 1; i < n - 1; i ++) {
if (i < j) a[i] ^= a[j] ^= a[i] ^= a[j];
for (k = n >> 1; (j ^= k) < k; k >>= 1);
}
for (l = 2, c = 1; l <= n; l <<= 1, c ++) {
_w = dft == -1 ? iww[c] : ww[c];
for (i = l >> 1, j = 0; j < n; j += l) for (k = 0; k < i; k ++) {
u = a[j + k] % P, v = (ll)a[j + k + i] * _w[k] % P;
a[j + k] = u + v, a[j + k + i] = u - v;
}
}
if (dft == -1) for (i = 0; i < n; i ++) a[i] = (ll)a[i] * inv[n] % P;
for (i = 0; i < n; i ++) a[i] = (a[i] % P + P) % P;
}
int x[N], y[N], z[N];
void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c) {
int l = fxt(n + m), i;
memcpy(x, a, n + 1), memcpy(y, b, m + 1);
fft(x, l, 1), fft(y, l, 1);
for (i = 0; i < l; i ++) z[i] = (ll)x[i] * y[i] % P;
fft(z, l, -1);
for (i = 0; i <= n + m; i ++) c[i] = z[i];
}