Fast Modular Power

Description:

Compute a to the power b modulo 10^9 + 7 where a, b <= 10^9

Implementation

#include <cstdio>
using namespace std;

typedef long long ll;
int mod = int(1e9) + 7;

ll fastModPow(int a, ll b, int &mod) {
  if( !b ) return 1;
  ll res = fastModPow(a, b / 2, mod);
  res *= res;
  if( res >= mod ) res %= mod;
  if( b % 2 ) res *= a;
  if( res >= mod ) res %= mod;

  return res;
}

int main( void ) {
  int a; ll b;
  scanf("%d %lld", &a, &b);

  printf("%lld\n", fastModPow(a, b, mod));

  return 0;
}

Notes

In the code above, I have used a reference to mod because it is less costly and the mod doesn't change over time and I declared the mod at the top as a global this is not necessary and varies depending on the problem on hand. This fasModPow function also helps in computing binomial coefficients especially if the mod is prime