#include <algorithm>
const int N = 1 << 21;
const int p = 81 << 21 | 1;
const int g = 1167 << 12 | 1;
const int h = 11443 << 12 | 1;
inline int pow_modp(int a, int b) { int x = 1; for(; b; a = (long long)a * a % p, b >>= 1) if(b & 1) x = (long long)x * a % p; return x; }
unsigned ntt_sup[N];
inline void ntt(auto a[], int n, const int g) {
auto b = ntt_sup, j = a, _j = a; int _n = n >> 1, i, k, _k, w, _w;
for(i = 1, w = pow_modp(g, (p - 1) / n); i < n; i <<= 1, w = (long long)w * w % p, std :: swap(a, b))
for(k = 0, j = a, _j = a + _n, _w = 1; k != n; k += i, _w = (long long)_w * w % p)
for(_k = k, k += i; _k != k; ++j, ++_j, ++_k);
// b[_k] = *j + *_j < p ? *j + *_j : *j + *_j - p,
// b[_k + i] = (long long)(*j + p - *_j) * _w % p;
if(b != ntt_sup) std :: copy(a, a + n, b);
}
void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c) {
ntt(a, n, g), ntt(b, n, g); for(int i = 0; i < n; ++i) a[i] = (long long)a[i] * b[i] % p; ntt(a, n, h);
int inv_n = pow_modp(n, p - 2); for(int i = 0; i < n; ++i) c[i] = (long long)a[i] * inv_n % p;
}