def gcd(a,b):
    if a == 0:
        return (b,0,1)
    else:
        g, y, x = gcd(b % a ,a)
        return (g, x-(b//a)*y,y)

def mod_inverse(a,m):
    g, x, y = gcd(a, m)
    if g != 1:
        raise Exception('Modular error')
    else:
        return x % m