Given Number a & N, compute a^N. [Optimal Solution: O(log N)].

pow_fast.cpp

// a^N using fast exponentiation
const int64_t M = (int64_t) 1e9+7;  // very big prime number

int64_t pow_fast (int64_t a, int64_t N) {
  int64_t ans = 1, x = a;
  while (N != 0) {
    if (N & 1)
      ans = ((ans % M) * x) % M;
    x = ((x % M) * x) % M;
    N >>= 1;
  }
  return ans % M;
}