Modulo FFT

const ll MOD = 786433;
const ll root = 3, st = 65536;

ll binpow(ll a, ll b)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = ans * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ans;
}

int rev(int x, int l)
{
    int ans = 0;
    for (int i = 0; i < l; i++)
        ans |= (((x >> i) & 1) << (l - i - 1));
    return ans;
}

const ll root_inv = binpow(root, MOD - 2);

void fft(vector<ll> &a, bool inv)
{
    int n = sz(a);
    int len = 0;
    while ((1 << len) < n)
        len++;
    for (int i = 0; i < n; i++)
    {
        int j = rev(i, len);
        if (j > i)
            swap(a[i], a[j]);
    }
    for (int l = 1; l < n; l *= 2)
    {
        ll w = binpow((inv ? root_inv : root), st / l / 2LL);
        for (int i = 0; i < n; i += 2 * l)
        {
            ll wp = 1;
            for (int j = 0; j < l; j++)
            {
                ll u = a[i + j], v = a[i + j + l] * wp % MOD;
                a[i + j] = u + v;
                if (a[i + j] >= MOD)
                    a[i + j] -= MOD;
                a[i + j + l] = u - v;
                if (a[i + j + l] < 0)
                    a[i + j + l] += MOD;
                wp = wp * w % MOD;
            }
        }
    }
    if (inv)
    {
        ll t = binpow(n, MOD - 2);
        for (int i = 0; i < n; i++)
            a[i] = a[i] * t % MOD;
    }
}

vector<ll> mult(const vector<ll> &a, const vector<ll> &b)
{
    int nn = sz(a) + sz(b) + 10;
    int n = 1;
    while (n < 2 * nn)
        n *= 2;
    n = min(n, st);
    vector<ll> aa(n, 0), bb(n, 0);
    for (int i = 0; i < sz(a); i++)
        aa[i] = a[i];
    for (int i = 0; i < sz(b); i++)
        bb[i] = b[i];
    fft(aa, 0);
    fft(bb, 0);
    for (int i = 0; i < n; i++)
        aa[i] = aa[i] * bb[i] % MOD;
    fft(aa, 1);
    while (sz(aa) && aa.back() == 0)
        aa.pop_back();
    return aa;
}