题目描述

求一个 \(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。

样例 #1

样例输入 #1

3
1 2 8
2 5 6
5 1 2

样例输出 #1

718750005 718750005 968750007
171875001 671875005 296875002
117187501 867187506 429687503

样例 #2

样例输入 #2

3
3 2 4
7 2 9
2 4 3

样例输出 #2

No Solution

提示

对 \(30 \%\) 的数据有 \(N\le 100\)；

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