线性代数（linear）

题目描述

（注意，你不需要掌握任何线性代数知识，在这里我们作的定义与实际定义不一样）

一个大小为 $n × n$ 的矩阵 $A$ ，有行列式 $|A|$。当其中某个位置 $(i, j)$ 在 $(j, j)$ 下方，即 $i > j$ 时，我们称这个位置在主对角线下方；同理，当 $(i, j)$ 满足 $i < j$ 时，我们称这个位置在主对角线上方；可以发现，其他位置 $(i, j)$ 一定在对角线上，即满足 $i = j$ 。如果矩阵满足所有非 $0$ 元素均在主对角线的上方或下方，这时这个矩阵的行列式等于它主对角线上所有数字的乘积。

如果这个矩阵不满足上述条件，则我们认为它的行列式不存在，输出None exist! 。

如果该矩阵的行列式存在，请将答案对 $10^9 + 7$取模。

！请使用文件输入输出！本题从linear.in中读取输入，将答案输出到linear.out中！直接从标准输入输出中读取/输出数据没有成绩！

输入格式

第一行一个正整数 $n$ ，含义如上。

接下来 $n$ 行，每行 $n$ 个非负整数，这其中第 $i$ 行第 $j$ 列上的数字表示矩阵 $A$ 中第 $i$ 行第 $j$ 列的值。

输出格式

唯一一行一个整数，表示矩阵的行列式对 $10^9 + 7$ 取模后的值，如果该行列式存在；

否则输出 None exist! 。

样例

【样例输入 1】

3
1 2 3
0 4 5
0 0 6

【样例输出 1】

24

【样例输入 2】

3
1 0 0
2 3 0
4 5 6

【样例输出 2】

18

【样例输入 3】

3
1 2 3
4 5 6
7 8 9

【样例输出 3】

None exist!

数据范围

对于 $100\%$ 的测试数据， $1 ≤ n ≤ 800, 0 ≤ A_{i,j} ≤ 100$ 。