def modpow(a, b, n):
    res = 1

    while b != 0:
        q, r = divmod(b, 2)

        if r == 1:
            res = (res * a) % n

        a = (a*a) % n
        b = q

    return res

def euclid(a, b):
    table = []
    current = [a, b]

    while current[1] != 0:
        a, b = current
        q, r = divmod(a, b)

        current.append(q)
        table.append(current)
        current = [b, r]

    table[-1] += [0, 1]

    while True:
        _, _, _, x, y = table.pop()

        if not table:
            return current[0], x, y

        _, _, q = table[-1]
        table[-1] += [y, x - q * y]

def modinv(a, n):
    _, x, _ = euclid(a, n)
    return x % n