public static void FFT(int[] A, int[] root, int n, int base, int[] Y) {
    int prod;
    if (n==1) {
      Y[base] = A[base];
      return;
      }
    inverseShuffle(A,n,base);	// inverse shuffle to separate evens and odds
    FFT(A,root,n/2,base,Y);	// results in Y[base] to Y[base+n/2-1]
    FFT(A,root,n/2,base+n/2,Y);	// results in Y[base+n/2] to Y[base+n-1]
    int j = A.length/n;
    for (int i=0; i<n/2; i++) {
      prod = (int)(((long)root[i*j]*Y[base+n/2+i]) % P);
      Y[base+n/2+i] = (int)(((long)Y[base+i] + P - prod) % P);
      Y[base+i] = (int)(((long)Y[base+i] + prod) % P);
      }
  }
  public static void inverseFFT(int[] A, int[] root, int n, int base, int[] Y) {
    int inverseN = modInverse(n);	// n^{-1}
    FFT(A,root,n,base,Y);
    for (int i=0; i<n; i++) 
      Y[i] = (int)(((long)Y[i]*inverseN) % P);
  }