Given three numbers a, b and m. The task is to find (a^b)%m.
Note: a is given as a String because it can be very big.
 
Example 1:
Input:
a = "3", b = 2, m = 4
Output:
1
Explanation:
(3^2)%4 = 9%4 = 1
Example 2:
Input:
a = "8", b = 2, m = 6
Output:
4
Explanation:
(8^2)%6 = 64%6 = 4 
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function powerMod() which takes a string a and 2 integers b, and m as input and returns (a^{b} % m).
 
Expected Time Complexity: O(Number of digits in a)
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= |a| <= 10^{5}
0 <= b <= 10^{9}
1 <= m <=10^{9}

Source: geeksforgeeks | Difficulty: EASY
Tags: Number theory

Starter code: #User function Template for python3



class Solution:

    def powerMod(self, a, b, m):

        # code here

Solutions:
class Solution:

	def powerMod(self, a, b, m):
		k = pow(int(a), b, m)
		return k % (10 ** 9 + 7)


class Solution:

	def powerMod(self, a, b, m):
		return pow(int(a), b, m)


class Solution:

	def powerMod(self, a, b, m):
		if b == 0:
			return 1 % m
		a = int(a) % m
		count = 1
		while b != 1:
			if b % 2 == 0:
				b = b // 2
			else:
				count = count * a % m
				b = (b - 1) // 2
			a = a * a % m
		return a * count % m


class Solution:

	def powerMod(self, a, b, m):
		res = 1
		a = int(a)
		a = a % m
		if a == 0:
			return 0
		while b > 0:
			if b & 1:
				res = res * a % m
			b = b >> 1
			a = a * a % m
		return res


class Solution:

	def helper(self, a, b, m):
		if b == 0:
			return 1
		if b == 1:
			return a
		x = self.helper(a, b // 2, m)
		if b % 2 == 0:
			return x * x % m
		else:
			return x * x * a % m

	def aModm(self, a, m):
		res = 0
		for i in a:
			res = (res * 10 + int(i)) % m
		return res

	def powerMod(self, a, b, m):
		a = self.aModm(a, m)
		if a == 0:
			return 0
		flag = 0
		if b < 0:
			flag = 1
		res = self.helper(a, b, m)
		return res if flag == 0 else 1 / res


def mod_exp(base, exp, mod):
	res = 1 % mod
	while exp:
		if exp & 1:
			res = res * base % mod
		base = base * base % mod
		exp >>= 1
	return res

class Solution:

	def powerMod(self, a, b, m):
		return mod_exp(int(a), int(b), int(m))