Линейное Диофантово уравнение

#!/usr/bin/env python3
 
def nod(m, n):
    return m if n == 0 else nod(n, m % n)
 
a = int(input("A = "))
b = int(input("B = "))
c = int(input("C = "))
 
assert c != 0
 
nodAB = nod(abs(a), abs(b))
if c % nodAB:
    print("Impossible")
else:
    a //= nodAB
    b //= nodAB
    c //= nodAB
 
    for k in range(abs(a)):
        if ( c - b * k ) % a == 0:
            y = k
            x = ( c - b * y ) // a
            print("X =", x, "Y =", y)
            break
    else:
        print("Shit happens!")

def gcd(a, b):
    while a != 0 and b != 0:
        if a < b:
            b = b % a
        else:
            a = a % b
    return a + b
 
 
def qwer(a, b): 
    x = 1 
    x1 = 0
    y = 0
    y1 = 1
    while b != 0:
        q = a // b
        r = a % b
        x2 = x - q * x1
        y2 = y - q * y1
        a, b = b, r
        x, x1 = x1, x2
        y, y1 = y1, y2
    return str(a), str(x), str(y)
    
 
a, b, c = list(map(int, input().split()))
x, y = 0, 0
gcds = 0
if c % gcd(a, b) != 0:
    print('Impossible')
else:
    gcds, x, y = map(int, qwer(a, b))
    x *= c // gcds
    y *= c // gcds
    q = x // (b // gcds)
    x %= b // gcds
    y += a // gcds * q
    print(x, y)