def extended_gcd(a, b):
    """
    Return r, s, t such that gcd(a, b) = r = a * s + b * t
    """
    r0, r1 = a, b
    s0, s1, t0, t1 = 1, 0, 0, 1
    if r0 > r1:
        r0, r1, s0, s1, t0, t1 = r1, r0, t0, t1, s0, s1
    while r1 > 0:
        q, r = divmod(r0, r1)
        r0, r1, s0, s1, t0, t1 = r1, r, s1, s0 - q * s1, t1, t0 - q * t1
    return r0, s0, t0