from fractions import Fraction

def gcd(x, y):
    def gcd1(x, y):
        if y == 0:
            return x
        return gcd1(y, x%y)
    return gcd1(abs(x), abs(y))

def simplify(x, y):
    g = gcd(x, y)
    return Fraction(long(x/g), long(y/g))

def lcm(x, y):
    return long(x*y/gcd(x,y))

def transform(m):
    sum_list = list(map(sum, m))
    bool_indices = list(map(lambda x: x == 0, sum_list))
    indices = set([i for i, x in enumerate(bool_indices) if x])
    new_m = []
    for i in xrange(len(m)):
        new_m.append(list(map(lambda x: Fraction(0, 1) if(sum_list[i] == 0) else simplify(x, sum_list[i]), m[i])))
    transform_m = []
    zeros_m = []
    for i in xrange(len(new_m)):
        if i not in indices:
            transform_m.append(new_m[i])
        else:
            zeros_m.append(new_m[i])
    transform_m.extend(zeros_m)
    t_m = []
    for i in xrange(len(transform_m)):
        t_m.append([])
        extend_m = []
        for j in xrange(len(transform_m)):
            if j not in indices:
                t_m[i].append(transform_m[i][j])
            else:
                extend_m.append(transform_m[i][j])
        t_m[i].extend(extend_m)
    return [t_m, len(zeros_m)]

def copy(m):
    c_m = []
    for i in xrange(len(m)):
        c_m.append([])
        for j in xrange(len(m[i])):
            c_m[i].append(Fraction(m[i][j].numerator, m[i][j].denominator))
    return c_m

def gauss_elmination(initial, values):
    m = copy(initial)
    for i in xrange(len(m)):
        index = -1
        for j in xrange(i, len(m)):
            if m[j][i].numerator != 0:
                index = j
                break
        if index == -1:
            raise ValueError('Gauss elimination failed!')
        m[i], m[index] = m[index], m[j]
        values[i], values[index] = values[index], values[i]
        for j in xrange(i+1, len(m)):
            if m[j][i].numerator == 0:
                continue
            ratio = -m[j][i]/m[i][i]
            for k in xrange(i, len(m)):
                m[j][k] += ratio * m[i][k]
            values[j] += ratio * values[i]
    res = [0 for i in xrange(len(m))]
    for i in xrange(len(m)):
        index = len(m) -1 -i
        end = len(m) - 1
        while end > index:
            values[index] -= m[index][end] * res[end]
            end -= 1
        res[index] = values[index]/m[index][index]
    return res

def transpose(m):
    t_m = []
    for i in xrange(len(m)):
        for j in xrange(len(m)):
            if i == 0:
                t_m.append([])
            t_m[j].append(m[i][j])
    return t_m

def inverse(m):
    t_m = transpose(m)
    m_inv = []
    for i in xrange(len(t_m)):
        values = [Fraction(int(i==j), 1) for j in xrange(len(m))]
        m_inv.append(gauss_elmination(t_m, values))
    return m_inv

def mult(m1, m2):
    res = []
    for i in xrange(len(m1)):
        res.append([])
        for j in xrange(len(m2[0])):
            res[i].append(Fraction(0, 1))
            for k in xrange(len(m1[0])):
                res[i][j] += m1[i][k] * m2[k][j]
    return res

def split(m, lengthR):
    lengthQ = len(m) - lengthR
    Q = []
    R = []
    for i in xrange(lengthQ):
        Q.append([int(i==j)-m[i][j] for j in xrange(lengthQ)])
        R.append(m[i][lengthQ:])
    return [Q, R]

def solution(m):
    res = transform(m)
    if res[1] == len(m):
        return [1, 1]
    Q, R = split(*res)
    inv = inverse(Q)
    res = mult(inv, R)
    row = res[0]
    l = 1
    for item in row:
        l = lcm(l, item.denominator)
    res = list(map(lambda x: long(x.numerator*l/x.denominator), row))
    res.append(l)
    return res