# Arup Guha
# 7/24/2013
# Fast Exponentiation

import time

def main():
    start = time.time()
    print(myModPow(185673623, 10000000, 1000000007))
    end = time.time()
    print("Your code took",(end-start),"seconds.")

    start = time.time()
    print(myModPowRec(185673623, 10000000, 1000000007))
    end = time.time()
    print("Your code took",(end-start),"seconds.")

# Typical modular exponentiation code with a for loop.
def myModPow(base,exp,mod):

    ans = 1
    for i in range(exp):
        ans = (ans*base)%mod

    return ans

# Fast Exponentiation - exploits short-cut for even exponents.
def myModPowRec(base,exp,mod):

    # Usual base cases.
    if exp == 0:
        return 1%mod
    elif exp == 1:
        return base%mod

    # This is the key - calculate the square root and square.
    elif exp%2 == 0:
        mysqrt = myModPowRec(base,exp//2,mod)
        return (mysqrt*mysqrt)%mod

    # Regular recursive break down.
    else:
        return (base*myModPowRec(base, exp-1, mod))%mod

    return ans

main()