For two given positive numbers a and b. Find a^{b}. Output your number modulus 10^{9}+7.
Example 1:
Input: a = 1, b = 1
Output: 1
Explanation: 1^{1} % (10^{9}+7) = 1
Ã¢â¬â¹Example 2:
Input: a = 2, b = 5
Output: 32
Explanation: 2^{5} % (10^{9}+7) = 32
Your Task:  
You don't need to read input or print anything. Your task is to complete the function power() which takes a, b as inputs, and returns the answer.
Expected Time Complexity: O(log b)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ a ≤ 10^{5}
1 ≤ b ≤ 10^{16}

Difficulty: EASY
Tags: Mathematics
Expected Time Complexity: O(log b)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3

class Solution:
    def power (self, a, b):
        #complete the function here

Solutions:
class Solution:

	def power(self, x, n):
		neg = False
		ans = 1
		mod = 10 ** 9 + 7
		if n < 0:
			neg = True
			n = -n
		while n != 0:
			if n % 2:
				ans = ans * x % mod
				n = n - 1
			else:
				x = x * x % mod
				n = n // 2
		if neg:
			ans = pow(ans, -1, mod)
		return ans % mod


class Solution:

	def power(self, a, b):
		return pow(a, b, 1000000007)


class Solution:

	def power(self, a, b):
		modulus = 1000000007
		result = 1
		while b > 0:
			if b % 2 == 0:
				a = a * a % modulus
				b //= 2
			else:
				result = result * a % modulus
				b -= 1
		return result


class Solution:

	def power(self, a, b):
		c = 10 ** 9 + 7
		a %= c
		if a == 0:
			return 0
		res = 1
		while b > 0:
			if b & 1 == 1:
				res = res * a % c
			b >>= 1
			a = a * a % c
		return res


class Solution:

	def power(self, a, b):
		return pow(a, b, 10 ** 9 + 7)


class Solution:

	def power(self, a, b):
		M = 1000000007
		if b == 1:
			return a % M
		ans = 1
		while b > 0:
			if b & 1 != 0:
				ans = ans * (a % M) % M
			a = a % M * (a % M) % M
			b = b >> 1
		return ans


class Solution:

	def power(self, a, b):
		h = 1000000007
		if b == 0:
			return 1
		if b == 1:
			return a
		res = 1
		while b > 0:
			if b & 1 == 1:
				res = res % h * a % h
			b = b >> 1
			a = a % h * a % h
		return res % h


class Solution:

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


class Solution:

	def power(self, a, b):
		m = 1000000007
		result = 1
		while b:
			if b % 2 != 0:
				result *= a
			b = b // 2
			a = a * a % m
		return result % m


class Solution:

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


class Solution:

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


class Solution:

	def power(self, a, b):
		m = 1000000007
		l = [a]
		c = 1
		while c < b:
			d = l[-1] * l[-1]
			l.append(d % m)
			c = c * 2
		s = bin(b)
		s = s[2:]
		s = s[::-1]
		p = 1
		d = 0
		for i in s:
			if i == '1':
				p = p * l[d]
			p = p % m
			d += 1
		return p


class Solution:

	def power(self, a, b):
		mod = 10 ** 9 + 7
		if b == 0:
			return 1
		halfPower = self.power(a, b // 2)
		result = 1
		if b % 2 == 0:
			result *= halfPower % mod * halfPower % mod
		else:
			result *= halfPower % mod * halfPower % mod * a
		return result % mod
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(a, b) = map(int, input().split())
		ob = Solution()
		print(ob.power(a, b))


import math

class Solution:

	def findPower(self, x, y, p):
		res = 1
		x = x % p
		while y > 0:
			if y & 1:
				res = res * x % p
			y = y >> 1
			x = x * x % p
		return res

	def power(self, a, b):
		b = str(b)
		rem = 0
		mod = 1000000007
		for i in range(len(b)):
			rem = (rem * 10 + ord(b[i]) - 48) % (mod - 1)
		return self.findPower(a, rem, mod)


class Solution:

	def power(self, a, b):
		m = 10 ** 9 + 7
		if b == 0:
			return 1
		res = self.power(a, b // 2)
		if b & 1:
			return a * (res * res) % m % m
		else:
			return res * res % m


class Solution:

	def power(self, a, b):
		MOD = 10 ** 9 + 7
		result = 1
		while b:
			if b & 1:
				result = result % MOD * (a % MOD)
			a = a % MOD * (a % MOD)
			b >>= 1
		return result % MOD


class Solution:
	cap = 1000000007

	def power(self, a, b):
		if b == 0:
			return 1
		elif a == 0:
			return 0
		else:
			res = self.power(a, int(b / 2))
			if b % 2 == 0:
				return res * res % self.cap
			else:
				return a * res * res % self.cap


class Solution:

	def power(self, a, b):
		x = a
		y = b
		p = 1000000007
		x = x % p
		if x == 0:
			return 0
		res = 1
		while y > 0:
			if y & 1 == 1:
				res = res * x % p
			y = y >> 1
			x = x * x % p
		return res % p


class Solution:

	def power(self, a, b):
		res = 1
		while b > 0:
			if b % 2 == 0:
				a = a * a % 1000000007
				b = b // 2
			else:
				res = res * a % 1000000007
				b = b - 1
		return res


class Solution:

	def power(self, x, y):
		res = 1
		m = 10 ** 9 + 7
		while y > 0:
			if y & 1 == 1:
				res = res * x % m
			y = y >> 1
			x = x * x % m
		return res % m


class Solution:

	def power(self, a, b):

		def findmodpow(a, b, m):
			res = 1
			while b > 0:
				if b & 1:
					res = res * a % m
				a = a * a % m
				b >>= 1
			return res
		return findmodpow(a, b, int(1000000000.0 + 7))


class Solution:

	def power(self, a, b):
		if b == 0:
			return 1
		base = a
		result_temp = self.power(a, b // 2)
		if b % 2 == 0:
			result = result_temp * result_temp
		else:
			result = base * result_temp * result_temp
		return result % (10 ** 9 + 7)