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

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
mod = 1000000007
def ipow(base, exp):
    result = 1
    while (exp != 0):
        if ((exp & 1) == 1):
            result = (result%mod * base%mod)%mod
        exp >>= 1
        base = (base%mod * base%mod)%mod
    return result;

a = raw_input()
b = raw_input()
print ipow(int (a), int(b))