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))

print (modexp(137, 55, 221))
print (modexp(137, 110, 221))
print (modexp(137, 220, 221))

def witness561(a):
    print (a, end=' ')
    print (modexp(a, 35, 561),end='')
    print (modexp(a, 70, 561),end=' ')
    print (modexp(a, 140, 561),end=' ')
    print (modexp(a, 280, 561),end=' ')
    print (modexp(a, 560, 561),end=' ')

# for HW 6 problem
print (modexp(437, 41, 703))
print (modexp(361, 569, 703))