NTT

将FFT中的的值改为,对取模即可,为的原根，
其中的值需要有足够大的的幂次因子
比如
将记作，在意义下与具有相同的性质

性质如下

1.为的原根，因此两两不相同
2.
3.
4.
所以可以与等价，用来快速变换

模板

void NTT(ll y[],int len,int rev)
{
    change(y,len);
    for(int h = 2; h <= len; h <<= 1)
    {
        ll wn = qmod(3, (mod - 1) / h);
        for (int j = 0; j < len; j += h)
        {
            ll w = 1;
            for (int k = j; k < j + h / 2; k++)
            {
                ll u = y[k];
                ll t = (w * y[k + h / 2]) % mod;
                y[k] = (u + t) % mod;
                y[k + h / 2] = (u - t + mod) % mod;
                w = (w * wn) % mod;
            }
        }
    }
    if (rev == -1)
    {
        reverse(y + 1, y + len);
        ll inv = qmod(len, mod - 2);
        for(int i = 0;i < len;i++)
            (y[i] *= inv) %= mod;
    }
}