def egcd(a, b):
    """
    Compute extended euclidean for `a` and `b`

    Pre-condition: a > b
    """
    if a % b == 0:
        return (None, None)
    mem = [0, 1, 0, None]
    while b != 1:
        t = mem[1]
        mem[1] = mem[0] - t * (a // b)
        mem[0] = t

        if mem[3] is None:
            mem[3] = 1
        else:
            t = mem[3]
            mem[3] = mem[2] - t * (a // b)
            mem[2] = t

        t = b
        b = a % b
        a = t
    return (mem[3], mem[1])