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
'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
def power(b, p,md):
    if p == 0:
        return 1;
    elif p%2 == 0:
        res = power(b, p/2,md)
        return (res*res)%md
    else:
    	res = power(b, p/2,md)
        return (((b*res)%md)*res)%md

a=int(raw_input())
b=str(raw_input())
m=int(10**9 + 7)
rem = 0
for i in range(len(b)):
	dvnd = (rem * 10) + int(b[i])
	rem = dvnd % (m-1)
	quot = dvnd / (m-1)


ans= power(a,rem,m)
print ans