FFT

    #define PI acos(-1.0)
    class point
    {
        public:
            double x,y;
            point(double _x=0,double _y=0){x=_x;y=_y;}
            point operator+(const point &t)const{return point(x+t.x,y+t.y);}
            point operator-(const point &t)const{return point(x-t.x,y-t.y);}
            point operator*(const point &t)const{return point(x*t.x-y*t.y,x*t.y+y*t.x);}
            void operator/=(const int n){x=x/n; y=y/n; return;}
            point conj()const{return point(x,-y);}
            double real()
            {
                return x;
            }
    };

    #define base point
    void fft(vector<base> &a,bool invert)
    {

        int n=a.size(),i,j;

        for(i=1,j=0;i<n;++i)    //Bit reverse
        {
            int bit=n>>1;
            for(;j>=bit;bit>>=1)
                j=j-bit;
            j=j+bit;
            if(i<j)
                swap(a[i],a[j]);
        }


        for(int len=2;len<=n;len<<=1)
        {
            ld ang=2*PI/len*(invert?-1:1);
            base wlen(cos(ang),sin(ang));
            for(i=0;i<n;i+=len)
            {
                base w(1);
                for(int j=0;j<len/2;++j)
                {
                    base u=a[i+j],v=a[i+j+len/2]*w;
                    a[i+j]=u+v;
                    a[i+j+len/2]=u-v;
                    w=w*wlen;
                }
            }
        }

        if(invert)
        {
            for(i=0;i<n;++i)
                a[i]/=n;
        }
    }
    vector<ll> res,a,b;

    void mul(const vector<ll> &a,const vector<ll> &b)
    {
        vector<base> fa(a.begin(),a.end()),fb(b.begin(),b.end());
        size_t n=1;
        int i;
        while(n<max(a.size(),b.size())) n<<=1;
        n<<=1;
        fa.resize(n),fb.resize(n);
        fft(fa,false);fft(fb,false);
        for(i=0;i<n;++i)
        {
            fa[i]=fa[i]*fb[i];
        }
        fft(fa,true);
        res.resize(n);
        for(i=0;i<n;++i)
            res[i]=(ll)(fa[i].real()+0.5);
    }
    ll s,sq;    //s=ceil(sqrt(mod)) and sq=(s*s)%mod
    void fft_modulo(const vector<ll> &a,const vector<ll> &b)
    {
        vector<ll> res1,res2,res3,res4,a1,a2,b1,b2;

        int i;
        ll x;
        for(i=0;i<a.size();++i)
        {
            x=a[i]%mod;
            a1.pb(x%s);
            a2.pb(x/s);
        }
        for(i=0;i<b.size();++i)
        {
            x=b[i]%mod;
            b1.pb(x%s);
            b2.pb(x/s);
        }
        mul(a1,b1);
        res1=res;
        res.clear();
        mul(a1,b2);
        res2=res;
        res.clear();
        mul(a2,b1);
        res3=res;
        res.clear();
        mul(a2,b2);
        res4=res;
        for(i=0;i<res.size();++i)
        {
            res[i]=(res1[i]+(((res2[i]+res3[i]))*s)+(((res4[i])*sq)))%mod;  //Add mods if needed for overflow
        }
    }