def egcd(a, b):
    """
    This function performs an extended GCD according to euclid's algorithm.
    It finds a pair (s, t) such that a*s + b*t == gcd
    """
    s0, s1, t0, t1 = 1, 0, 0, 1
    while b > 0:
        q, r = divmod(a, b)
        a, b = b, r
        s0, s1, t0, t1 = s1, s0 - q * s1, t1, t0 - q * t1
    return s0, t0, a