def mod_inverse(a, m):
    """Return a^-1 mod m (modular inverse)"""

    def egcd(a, b):
        """Return an extended greatest common divisor for a, b"""
        if a == 0:
            return b, 0, 1
        g, y, x = egcd(b % a, a)
        return g, x - y*(b // a), y

    g, x, y = egcd(a, m)
    if g != 1:
        raise ValueError("No modular inverse for: a={:d}, m={:d}".format(a, m))

    return x % m