def finiteInverse(a, p):
    """Compute 1/a mod p using the Euclidean algorithm."""
    x = [a % p, 1, 0]
    y = [p, 0, 1]
    while x[0] != 1:
        z = divmod(y[0], x[0])
        x, y = [z[1], y[1] - z[0] * x[1], y[2] - z[0] * x[2]], x
    return x[1] % p
