Given a number and its reverse. Find that number raised to the power of its own reverse.
Note: As answers can be very large, print the result modulo 10^{9} + 7.
Example 1:
Input:
N = 2
Output: 4
Explanation: The reverse of 2 is 2 and after raising power of 2 by 2 we get 4 which gives remainder as 4 when divided by 1000000007.
Example 2:
Input:
N = 12
Output: 864354781
Explanation: The reverse of 12 is 21and 12^{21} when divided by 1000000007 gives remainder as 864354781.
Your Task:
You don't need to read input or print anything. You just need to complete the function pow() that takes two parameters N and R denoting the input number and its reverse and returns power of (N to R)mod(10^{9} + 7).
Expected Time Complexity: O(LogN).
Expected Auxiliary Space: O(LogN).
Constraints:
1 <= N <= 10^{9}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Divide and conquer

Mathematics

Complete search

Starter code: #User function Template for python3

class Solution:
    #Complete this function
    def power(self,N,R):
        #Your code here

Solutions:
class Solution:

	def power(self, N, R):
		if R == 0:
			return 1
		elif R % 2 == 0:
			return self.power(N, R // 2) ** 2 % (10 ** 9 + 7)
		else:
			return N * self.power(N, R // 2) ** 2 % (10 ** 9 + 7)


import math

class Solution:

	def power(self, N, R):
		mod = pow(10, 9) + 7
		if R == 0:
			return 1
		elif R % 2 == 0:
			temp = self.power(N, R / 2) % mod
			return temp * temp % mod
		else:
			temp = self.power(N, R - 1) % mod
			return N * temp % mod


class Solution:

	def power(self, N, R):
		if R == 0:
			return 1
		if R % 2 == 0:
			x = self.power(N, R // 2) ** 2
		else:
			x = N * self.power(N, (R - 1) // 2) ** 2
		return x % 1000000007


class Solution:

	def power(self, N, R):

		def cal_power(num, power, value=1):
			temp_num = num * num
			temp_power = power
			temp_val = value
			if power == 0:
				return value
			if power == 1:
				return value * num
			if power % 2 == 0:
				temp_power = temp_power // 2
			else:
				temp_power = (temp_power - 1) // 2
				temp_val = num * temp_val
			return cal_power(temp_num % 1000000007, temp_power, temp_val % 1000000007)
		return cal_power(N, R) % 1000000007


class Solution:

	def power(self, N, R):
		MOD = pow(10, 9) + 7

		def power_recursive(R):
			if R == 1:
				return N
			temp = power_recursive(R // 2)
			if R % 2 == 0:
				return temp * temp % MOD
			else:
				return N * temp * temp % MOD
		return power_recursive(R) % MOD


class Solution:

	def power(self, N, R):
		mod = 1000000007
		res = 1
		while R > 0:
			if R % 2:
				res = res * N % mod
			N = N * N % mod
			R = R // 2
		return res


class Solution:

	def power(self, N, R):

		def fun(N, R):
			if R == 1:
				return N
			temp = fun(N, R // 2) % 1000000007
			temp = temp * temp % 1000000007
			if R % 2 == 0:
				return temp % 1000000007
			else:
				return N * temp % 1000000007
		return fun(N, R)


class Solution:

	def power(self, N, R):
		r = R
		ans = 1
		while r:
			if r % 2:
				ans = ans * N % (10 ** 9 + 7)
				r -= 1
			else:
				N = N * N % (10 ** 9 + 7)
				r //= 2
		return ans % (10 ** 9 + 7)


class Solution:

	def power(self, N, R):
		mod = 1000000007
		result = pow(N, R, mod)
		return result


class Solution:

	def power(self, N, R):
		mod = 1000000007
		if N == 0:
			return 0
		if R == 0:
			return 1

		def rec_power(N, R):
			if R == 0:
				return 1
			elif R == 1:
				return N
			elif R % 2 == 0:
				ans = rec_power(N, R // 2)
				return ans * ans % mod
			else:
				ans = rec_power(N, (R - 1) // 2)
				return ans * ans * N % mod
		return rec_power(N, R)


class Solution:

	def power(self, N, R):
		a = N
		res = 0
		while N > 0:
			d = N % 10
			res = res * 10 + d
			N = N // 10
		return pow(a, res, 10 ** 9 + 7)


class Solution:

	def power(self, N, R):
		return self.pow(N, R, 1000000007)

	def pow(self, N, R, M):
		if R == 0:
			return 1
		elif R % 2 == 0:
			a = self.pow(N, R // 2, M)
			return a % M * (a % M) % M
		else:
			a = self.pow(N, R - 1, M)
			return a % M * (N % M) % M


class Solution:

	def modfun(self, N, R):
		if N == 0:
			return 0
		if R == 0:
			return 1
		y = 0
		if R % 2 == 0:
			y = self.modfun(N, R / 2)
			y = y * y % 1000000007
		else:
			y = N % 1000000007
			y = y * self.modfun(N, R - 1) % 1000000007 % 1000000007
		return (y + 1000000007) % 1000000007

	def power(self, N, R):
		return self.modfun(N, R)


class Solution:

	def power(self, num, rev):
		ans = 1
		mod = 10 ** 9 + 7
		pow = num * 1
		while rev > 0:
			if rev % 2 == 1:
				ans = ans * pow % mod
			pow = pow * pow % mod
			rev >>= 1
		return ans


class Solution:

	def power(self, N, R):

		def pow_x(x, n, mod):
			if x == 0:
				return 0
			elif n == 0:
				return 1
			res = pow_x(x * x % mod, n // 2, mod)
			return x * res % mod if n % 2 else res
		mod = int(1000000000.0 + 7)
		res = pow_x(N, R, mod)
		return res % mod


class Solution:

	def power(self, N, R):
		nn = R
		ans = 1
		if R < 0:
			R = -1 * R
		while R > 0:
			if R % 2 == 0:
				N = N * N
				N = N % 1000000007
				R = R / 2
			else:
				ans = ans * N
				ans %= 1000000007
				R = R - 1
		if nn < 0:
			return 1 / ans
		return ans


def power(a, n, mod):
	res = 1
	a = a % mod
	if a == 0:
		return 0
	while n > 0:
		if n & 1 == 1:
			res = res * a % mod
		n = n >> 1
		a = a * a % mod
	return res
MOD = int(1000000000.0 + 7)

class Solution:

	def power(self, N, R):
		return power(N, R, MOD)


import sys

class Solution:

	def __init__(self):
		sys.setrecursionlimit(20000)
	M = 10 ** 9 + 7

	def power(self, N, R):
		if R == 0:
			return 1
		temp = self.power(N, R // 2)
		temp = temp * temp % 1000000007
		if R % 2 == 0:
			return temp % 1000000007
		else:
			return temp * N % 1000000007


import math

class Solution:

	def power(self, N, R):
		if R == 0:
			return 1
		temp = self.power(N, R // 2)
		temp = temp * temp % 1000000007
		if R % 2 == 0:
			return temp % 1000000007
		else:
			return temp * N % 1000000007


class Solution:

	def power(self, N, R):
		if R == 0:
			return 1
		temp = self.power(N, R // 2) % 1000000007
		sq = temp * temp % 1000000007
		if R % 2 == 0:
			return sq
		return N * sq % 1000000007


class Solution:

	def power(self, N, R):
		number = N
		reverse = 0
		mod = 1000000007
		while N != 0:
			digit = N % 10
			reverse = reverse * 10 + digit
			N //= 10

		def p(n, reverse):
			if reverse == 0:
				return 1
			elif reverse % 2 == 0:
				subproblem = p(number, reverse // 2)
				return subproblem * subproblem % mod
			else:
				subproblem = p(number, reverse - 1)
				return number * subproblem % mod
		return p(number, reverse)


class Solution:

	def power(self, N, R):

		def funcall(N, R):
			if R == 1:
				return N
			if R == 2:
				return N * N % 1000000007
			if R % 2 == 1:
				ans = N * funcall(N, R - 1) % 1000000007
				return ans
			else:
				ans = funcall(N, R // 2)
				ans = ans * ans % 1000000007
				return ans
		return funcall(N, R)


class Solution:
	memo = []

	def power(self, N, R):
		if R == 0:
			return 1
		if R % 2 == 0:
			ans = self.power(N, R / 2)
			return ans % 1000000007 * ans % 1000000007 % 1000000007
		else:
			ans = self.power(N, (R - 1) / 2)
			return ans % 1000000007 * ans % 1000000007 * N % 1000000007 % 1000000007


class Solution:

	def power(self, N, R):
		return pow(N, R, 10 ** 9 + 7)


class Solution:

	def power(self, N, R):
		return pow(N, R, 1000000007)


class Solution:

	def power(self, N, R):
		if R == 0:
			return 1
		solve = self.power(N, R // 2)
		sq = solve * solve
		if R % 2 == 0:
			return sq % (10 ** 9 + 7)
		return N * sq % (10 ** 9 + 7)


class Solution:

	def power(self, N, R):
		mod = 10 ** 9 + 7
		res = 1
		while R > 0:
			if R % 2 == 1:
				res = res * N % mod
			N = N * N % mod
			R //= 2
		return res


class Solution:

	def power(self, N, R):
		if R // 10 == 0:
			return N ** R % (10 ** 9 + 7)
		else:
			Rdivide10 = R // 10
			digitR = R % 10
			return N ** digitR % (10 ** 9 + 7) * self.power(N ** 10 % (10 ** 9 + 7), Rdivide10) % (10 ** 9 + 7)


class Solution:

	def power(self, N, R):
		K = 10 ** 9 + 7
		ans = 1
		while R > 0:
			if R & 1:
				ans = ans * N % K
			N = N * N % K
			R = R >> 1
		return ans