# Szybkie potegowanie modularne
# www.algorytm.org
#
# tested with Python 3.3
# license: Public Domain

def fme(a, k, n):
	"""
	modular exponentiation
	a ** k mod n
	"""
	b = bin(k)[2:] # list of bits
	m = len(b)
	r = 1 # result
	x = a % n

	for i in range(m - 1, -1, -1):
		if b[i] == '1':
			r = r * x % n

		x **= 2
		x  %= n

	return r

# Python built-in alternative:
#     pow(a, k, n)