#!/usr/bin/python3

bitlength = 128
p = 101
#p = 2003

def multiply(i, j):
	n = i
	r = 0
	for bit in range(bitlength):
		if (j & (1 << bit)):
			r = (r + n) % p
		n = (n + n) % p
	return r

def exponentiate(i, j):
	n = i
	r = 1
	for bit in range(bitlength):
		if (j & (1 << bit)):
			r = multiply(r, n)
		n = multiply(n, n)
	return r

def eea(a, b):
	assert(isinstance(a, int))
	assert(isinstance(b, int))
	(s, t, u, v) = (1, 0, 0, 1)
	while b != 0:
		(q, r) = (a // b, a % b)
		(unew, vnew) = (s, t)
		s = u - (q * s)
		t = v - (q * t)
		(a, b) = (b, r)
		(u, v) = (unew, vnew)
	return (a, u, v)


print(exponentiate(2, 473289743783748378))
print(multiply(99, 77))
print(exponentiate(99, 77))

print(eea(77, p))
print((eea(77, p)[2] * 77) % p)