# Arup Guha
# 6/22/2017
# Fast Modular Exponentiation

# Goal: Calculate (b raised to the power e) mod n

def main():
    print(modpowfast(12345,5432111732631543126451364152271257451247511,1000000007))
    #print(modpowslow(12345,54321111,1000000007))
    
def modpowslow(base,exp,n):
    ans = 1
    for i in range(exp):
        ans = (ans*base)%n
    return ans

def modpowfast(base,exp,n):
    if exp == 0:
        return 1
    if exp%2 == 0:
        tmp = modpowfast(base,exp//2,n)
        return (tmp*tmp)%n

    return (base*modpowfast(base,exp-1,n))%n

main()