# -*- coding: cp1251 -*-
# Extended Euclidean algorithm
def xgcd(x,y):
    a0=1; b0=0
    a1=0; b1=1
    if x<0:
    	x *= -1
    	a0 = -1
    if y<0:
    	y *= -1
    	b1 = -1
    if x<y:
    	x,y,a0,b0,a1,b1 = y,x,a1,b1,a0,b0
    while 1:
    	times = x/y
    	x -= times*y
    	a0 -= times*a1
    	b0 -= times*b1
    	if x==0:
    		break
    	x,y,a0,b0,a1,b1 = y,x,a1,b1,a0,b0
    return [y,a1,b1]

# Find multiplicative inverse
def invmod(x,p):
	[gcd,a,b] = xgcd(x,p)
	if gcd != 1:
		raise ValueError
	if a<0:
		a += p;
	return a