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

pow_slow.cpp

// Naive Solution: O(N) Time Complexity
const long long M = (long long) 1e9+7;  // a very big prime number
long long pow(a, N) {
  if (N == 0) return 1;
  long long ans = 1;
  for(int i = 0; i < N; ++i)
    ans = ((ans % M) * a) % M;
  return ans % M;
}