Modular Exponentiation for large numbers

Implement pow(x, n) % M.

In other words, given x, n and M, find (xn) % M.

• Time : O(logn)
• Space : O(1)

class Solution
{
	public:
		long long int PowMod(long long int x,long long int n,long long int M)
		{
		    if(n == 1) return x % M;
		    long long int res = PowMod(x, n>>1, M);
		    res = (res * res) % M;
		    if(n & 1) res = (res * x) % M;
		    return res;
		}
};