def inverse_mod(a, p):
    """
    Compute the modular inverse of a (mod p)

    :param a:
        An integer

    :param p:
        An integer

    :return:
        An integer
    """
    if a < 0 or p <= a:
        a = a % p
    c, d = a, p
    uc, vc, ud, vd = 1, 0, 0, 1
    while c != 0:
        q, c, d = divmod(d, c) + (c,)
        uc, vc, ud, vd = ud - q * uc, vd - q * vc, uc, vc
    assert d == 1
    if ud > 0:
        return ud
    else:
        return ud + p
