protected static int modInverse(int n) { // assumes n is power of two
    int result = 1;
    for (long twoPower = 1; twoPower < n; twoPower *= 2)
      result = (int)(((long)result*TWOINV) % P);
    return result;
  }
  protected static void inverseShuffle(int[] A, int n, int base) {
    int shift;
    int[] sp = new int[n];
    for (int i=0; i<n/2; i++) {	// Unshuffle A into the scratch space
      shift = base + 2*i;
      sp[i] = A[shift];		// an even index
      sp[i+n/2] = A[shift+1];	// an odd index
      }
    for (int i=0; i<n; i++)
      A[base+i] = sp[i];	// copy back to A
  }
  protected static int[] rootsOfUnity(int n) { //assumes n is power of 2
    int nthroot = OMEGA;
    for (int t = MAXN; t>n; t /= 2) 	// Find prim. nth root of unity 
      nthroot = (int)(((long)nthroot*nthroot) % P);
    int[] roots = new int[n];
    int r = 1;		// r will run through all nth roots of unity
    for (int i=0; i<n; i++) {
      roots[i] = r;
      r = (int)(((long)r*nthroot) % P);
      }
    return roots;
  }
  protected static void propagateCarries(int[] A) {
    int i, carry;
    carry = 0;
    for (i=0; i<A.length; i++) {
      A[i] = A[i] + carry;
      carry = A[i] >>> ENTRYSIZE;
      A[i] = A[i] - (carry << ENTRYSIZE);
      }
    }