Matrix Inversion Modulo 10^9+7

Given an N×N matrix A with integer entries, compute its inverse matrix A^-1 under modulo 10^9+7.

This means you need to find a matrix B such that:

\[ A \times B \equiv I \pmod{10^9+7} \]

It is guaranteed that the inverse exists.

inputFormat

The first line contains an integer N, the size of the matrix.

The next N lines each contain N space-separated integers, representing the rows of the matrix A. All integers are given modulo 10^9+7.

outputFormat

Output the inverse matrix of A modulo 10^9+7 in N lines. Each line should contain N space-separated integers.

sample

1
1

1