# -*- mode: snippet -*-
# name: mod inverse
# contributor: Bhuvnesh Jain
# key: modinverse
# --
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

def mod_inverse(a, n):
	N = n
	xx = 0
	yy = 1
	y = 0
	x = 1
	while(n > 0):
		q = a // n
		t = n
		n = a % n
		a = t
		t = xx
		xx = x - q * xx
		x = t
		t = yy
		yy = y - q * yy
		y = t
	x %= N
	x += N
	x %= N
	return x
