Simple recursive function for exponentiation in O(log(n)) time with Mod.

PowMod_recursive.cpp

//recursive version
int64_t powMod(int64_t base,int64_t expo)
{
	if(expo==0)
	{
		return 1;
	}
	else if(expo%2==0)
	{
		int64_t ans=powMod(base,expo/2);
		return ans*ans%MOD;
	}
	else
	{
		return base*powMod(base,expo-1)%MOD;
	}
}