def modexp(x, y, N):
    if y==0: 
        return 1
    z = modexp(x, y/2, N)
    if y%2 == 0: 
        return (z*z) % N
    return (x* z*z) % N

print modexp(3, 4, 8)
print modexp(2, 10, 1000)
print modexp(2, 12, 100)