#include <algorithm>
#include <math.h>
using namespace std;
const int N = 4e6 + 5;
using ll = long long;
const ll P = 119 << 23 | 1, G = 3;
ll eps[N], a1[N], a2[N];
ll qpow(ll x, ll y) {
ll ans = 1;
for (; y; y >>= 1, x = x * x % P) {
if (y & 1) ans = ans * x % P;
}
return ans;
}
ll inv(ll x) { return qpow(x, P - 2); }
void init(int n) {
ll g = qpow(G, (P - 1) / n);
int l = n >> 1;
for (int i = eps[l] = 1; i < l; ++i) {
eps[l + i] = eps[l + i - 1] * g % P;
}
while (l >>= 1) {
for (int i = 0; i < l; ++i) {
eps[l + i] = eps[l + i << 1];
}
}
}
void dft(int n, ll x[]) { // output revbin
for (int i = n; i >= 2; i >>= 1) {
for (int j = 0, l = i >> 1; j < n; j += i) {
for (int k = 0; k < l; ++k) {
ll u = x[j + k], v = x[j + k + l];
x[j + k] = (u + v) % P, x[j + k + l] = (u - v) * eps[l + k] % P;
}
}
}
}
void idft(int n, ll x[]) { // input revbin
for (int i = 2; i <= n; i <<= 1) {
for (int j = 0, l = i >> 1; j < n; j += i) {
for (int k = 0; k < l; ++k) {
ll u = x[j + k], v = eps[l + k] * x[j + k + l];
x[j + k] = (u + v) % P, x[j + k + l] = (u - v) % P;
}
}
}
reverse(x + 1, x + n);
ll in = inv(n);
for (int i = 0; i < n; ++i) x[i] = (x[i] + P) * in % P;
}
void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c) {
for (int i = 0; i <= n; ++i) a1[i] = a[i];
for (int i = 0; i <= m; ++i) a2[i] = b[i];
int len = 1;
while (len < n + m + 2) len <<= 1;
init(len);
dft(len, a1), dft(len, a2);
for (int i = 0; i < len; ++i) (a1[i] *= a2[i]) %= P;
idft(len, a1);
for (int i = 0; i <= n + m; ++i) c[i] = a1[i];
}