# Arup Guha
# 10/25/2019

import time

# Usual way to exponentiate.
def slowmodexpo(base,exp,mod):
    ans = 1
    for i in range(exp):
        ans = (ans*base)%mod
    return ans

# Returns (base**exp) % mod, efficiently.
def fastmodexpo(base,exp,mod):

    # Base case.
    if exp == 0:
        return 1

    # Speed up here with even exponent.
    if exp%2 == 0:
        tmp = fastmodexpo(base,exp//2,mod)
        return (tmp*tmp)%mod

    # Odd case, must just do the regular ways.
    return (base*fastmodexpo(base,exp-1,mod))%mod


def main():

    # Small enough test for us to run both but see time difference.
    start = time.time()
    print(slowmodexpo(17,13500000,837123751236))
    end1 = time.time()
    print(fastmodexpo(17,13500000,837123751236))
    end2 = time.time()
    print("slow took",end1-start,"fast took",end2-end1)

    # We can only run the fast one on this.
    print(fastmodexpo(17,1354576253461235716563571521341234124124,833215621365416547236145613454571326457123751236))

# Run it!
main()