【模板】矩阵求逆

题目描述

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

输入输出格式

输入格式


第一行有一个整数$N$,代表矩阵的大小; 从第$2$行到第$N+1$行,每行$N$个整数,其中第$i+1$行第$j$列的数代表矩阵中的元素$a_{ij}$。

输出格式


若矩阵可逆,则输出$N$行,每行$N$个整数,其中第$i$行第$j$列的数代表逆矩阵中的元素 $b_{ij}$,答案对$10^9+7$取模; 否则只输出一行 `No Solution`。

输入输出样例

输入样例 #1

3
1 2 8
2 5 6
5 1 2

输出样例 #1

718750005 718750005 968750007
171875001 671875005 296875002
117187501 867187506 429687503

输入样例 #2

3
3 2 4
7 2 9
2 4 3

输出样例 #2

No Solution

说明

对30%的数据有$N\le 100$; 对100%的数据有$N\le 400$,所有$a_{ij}<10^9+7$。 ps.TLE的同学可以试试大力卡常,标算不开O2勉强能卡过去的