Problem: Rhezo likes numbers of the form A^B. But computing A^B, for any 2 numbers A and B is a hard task for him. He would like you to help him out in this.

Input:
First line of input contains a single integer A. Second line contains the integer B.

Output:
Help Rhezo find A^B. As this number can be large, print it modulo 10^9+7.

Constraints:
 1 ≤ A ≤ 10^9  
 1 ≤ B ≤ 10^{10^5} 

SAMPLE INPUT
4
3

SAMPLE OUTPUT
64

Solution (in PYTHON):

Solution:
import sys

def bigpow(a, b, m):
    bint = int(b)
    bfrac = b - int(b)
    return (pow(a, bint, m) * ((a**bfrac)%m)) % m

def main():
	a = int(raw_input())
	b = int(raw_input())
	
	print bigpow(a, b,1000000007) % 1000000007
	'''
	ans = 1
	for i in xrange(int(b)):
		ans *= a
		ans %= 1000000007
	print ans
	'''
main()