def egcd(a, b):
    """Return (s,t,d), such that d = gcd(a,b), and s*a + t*b = d."""
    if b == 0:
        return (1, 0, a)
    else:
        (s, t, d) = egcd(b, a % b)
        return (t, s - t * (a / b), d)