def modinv(base: int, mod: int) -> int:
    """
    Returns the modular inverse of base % mod.

    :param base: the base
    :param mod: the modulus
    :return: the modular inverse
    """
    try:
        return pow(base, -1, mod)
    except ValueError:
        # For Python <=3.7
        g, _g = base, mod
        x, _x = 1, 0

        while _g:
            q = g // _g
            g, _g = _g, (g - q * _g)
            x, _x = _x, (x - q * _x)

        if g > 1:
            raise ValueError("There is no inverse for {} mod {}".format(base, mod))

        if x < 0:
            x = x + mod

        return x