// FFT with modulo:
// GEN ^ LEN == 1 mod BASE
// GEN ^ (LEN / 2) != 1 mod BASE
// for prime modulo c2^k+1 generator for len 2^k exists always
const int LEN = 1<<20;    // max length, power of 2
const int BASE = 7340033; // modulo
const int GEN = 5;        // generator
int PW[LEN];              // powers of generator
void fft(vector<int>& a, bool invert)
{
    int lg = 0;
    while((1<<lg) < SZ(a)) lg++;

    FOR (i, 0, SZ(a))
    {
        int x=0;
        FOR (j, 0, lg)
            x |= ((i>>j)&1)<<(lg-j-1);
        if(i<x)
            swap(a[i], a[x]);
    }

    for (int len = 2; len <= SZ(a); len *= 2)
    {
        int diff = LEN / len;
        if (invert) diff = LEN - diff;
        for (int i = 0; i < SZ(a); i += len)
        {
            int pos = 0;
            FOR (j, 0, len/2)
            {
                int w = PW[pos];

                int v = a[i+j];
                int u = (a[i+j+len/2] * (LL) w) % BASE;

                int t = v + u;
                if (t >= BASE) t -= BASE;
                a[i+j] = t;

                t = v - u;
                if (t < 0) t += BASE;
                a[i+j+len/2] = t;

                pos += diff;
                if (pos >= LEN) pos -= LEN;
            }
        }
    }

    if (invert)
    {
        int m = inv(SZ(a), BASE);
        FOR (i, 0, SZ(a))
            a[i] = (a[i] * (LL)m) % BASE;
    }
}