题目描述

求一个 $N\times N$ 的矩阵的逆矩阵。答案对 ${10}^9+7$ 取模。

输入格式

第一行有一个整数 $N$，代表矩阵的大小；

接下来 $N$ 行，每行 $N$ 个整数，其中第 $i$ 行第 $j$ 列的数代表矩阵中的元素 $a_{i j}$。

输出格式

若矩阵可逆，则输出 $N$ 行，每行 $N$ 个整数，其中第 $i$ 行第 $j$ 列的数代表逆矩阵中的元素 $b_{i j}$，答案对 ${10}^9+7$ 取模；

否则只输出一行 No Solution。

3
1 2 8
2 5 6
5 1 2

718750005 718750005 968750007
171875001 671875005 296875002
117187501 867187506 429687503

3
3 2 4
7 2 9
2 4 3

No Solution

提示

对 $30 \%$ 的数据有 $N\le 100$；
对 $100 \%$ 的数据有 $N\le 400$，所有 $0 \le a_{i j} < {10}^9 + 7$。