#include <string.h>
#include <stdlib.h>
#include <math.h>
using namespace std;
typedef __uint128_t uint128;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef long long ll;
const int N = 2100005, M = 8400005, P = 998244353, g = 3, G = 25;
struct Div{
ull m,x;
int s;
Div(){}
Div(ull mo):m(mo){
s=__lg(mo-1);
x=(((uint128)1<<(s+64))+m-1)/m;
}
friend ull operator/(ull a,Div d){
return (((uint128)a*d.x)>>d.s)>>64;
}
friend ull operator%(ull a,Div d){
return a-a/d*d.m;
}
}mo(P);
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 % mo;
return r;
}
int pol[M], *ed = pol, *ww[G], *iww[G], *_w;
int *nint (int len) { int *r = ed; ed += len; return r; }
void init (int n) {
register 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 % mo, iww[i][k] = (ll)iww[i][k - 1] * iw % mo;
}
}
void fft (int a[], int n, int dft) {
register 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] % mo, v = (ll)a[j + k + i] * _w[k] % mo;
a[j + k] = u + v, a[j + k + i] = u + P - v;
}
}
if (dft == -1) for (v = fpow(n, P - 2), i = 0; i < n; i ++) a[i] = (ll)a[i] * v % mo;
for (i = 0; i < n; i ++) a[i] %= 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;
init(l), memcpy(x, a, (n + 1) << 2), memcpy(y, b, (m + 1) << 2);
fft(x, l, 1), fft(y, l, 1);
for (i = 0; i < l; i ++) z[i] = (ll)x[i] * y[i] % mo;
fft(z, l, -1);
for (i = 0; i <= n + m; i ++) c[i] = z[i];
}