def modinv(a, m):
    """Find the modular inverse of a, with modulus m."""
    x = 0
    lastx = 1
    y = 1
    lasty = 0
    b = m
    while b != 0:
        a, (q, b) = b, divmod(a, b)
        x, lastx = lastx - q * x, x
        y, lasty = lasty - q * y, y
    return lastx % m
