Bobo 在 ICPCCamp 中学习了矩阵 $A$ 的行列式 $\mathrm{det}(A)$ 的定义。他还知道行列式可以通过高斯消元法在 $O(n^3)$ 的时间内计算出来。

Bobo 有一个 $n \times n$ 的矩阵 $B$，他想要计算所有 $i, j \in \{1, 2, \dots, n\}$ 的 $\mathrm{det}(B_{i,j})$ 对 $(10^9+7)$ 取模的结果，其中 $B_{i, j}$ 是从 $B$ 中删去第 $i$ 行和第 $j$ 列后得到的矩阵。

保证 $B$ 的每一列之和都是 $(10^9+7)$ 的倍数。

输入格式

输入包含零个或多个测试用例，并以文件结束符（EOF）终止。对于每个测试用例：

第一行包含一个整数 $n$。 接下来的 $n$ 行中，第 $i$ 行包含 $n$ 个整数 $B_{i, 1}, B_{i, 2}, \dots, B_{i, n}$。

• $2 \leq n \leq 500$
• $0 \leq B_{i, j} < 10^9 + 7$
• $n$ 的总和不超过 $5000$。

输出格式

对于每个测试用例，输出 $n$ 行，其中第 $i$ 行包含 $n$ 个整数 $\mathrm{det}(B_{i,1}), \mathrm{det}(B_{i, 2}), \dots, \mathrm{det}(B_{i, n})$ 对 $(10^9+7)$ 取模的结果。

样例

样例输入 1

2
0 1
0 1000000006

样例输出 1

1000000006 0
1 0