public static void FFT(int[] A, int[] root, int n) {
    int prod,term,index;	// Values for common subexpressions
    int subSize = 1;		// Subproblem size 
    bitReverse(A,logN);		// Permute A by bit reversal table
    for (int lev=1; lev<=logN; lev++) {
      subSize *= 2; 		// Double the subproblem size.
      for (int base=0; base<n-1; base += subSize) { // Iterate subproblems
	int j = subSize/2;
	int rootIndex = A.length/subSize;
	for (int i=0; i<j; i++) {
	  index = base + i;
	  prod = (int) (((long)root[i*rootIndex]*A[index+j]) % P);
	  term = A[index];
	  A[index+j] = (int) (((long)term + P - prod) % P);
	  A[index] = (int) (((long)term + prod) % P); 
	  }
	}
      }
  }
  public static void inverseFFT(int[] A, int[] root, int n) {
    int inverseN = modInverse(n);	// n^{-1}
    FFT(A,root,n);
    for (int i=0; i<n; i++) 
      A[i] = (int) (((long)A[i]*inverseN) % P);
  }