A. 线性代数

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

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

一个大小为 的矩阵 ,有行列式 。当其中某个位置 下方,即 时,我们称这个位置在主对角线下方;同理,当 满足 时,我们称这个位置在主对角线上方;可以发现,其他位置 一定在对角线上,即满足 。锐哥知道,如果矩阵满足所有非 元素均不在主对角线的上方或下方,这时这个矩阵的行列式等于它主对角线上所有数字的乘积。

如果这个矩阵不满足上述条件,则锐哥认为它的行列式不存在。因此他会大声说出自己喜欢的游戏的名字:

如果该矩阵的行列式存在,请将答案对 取模。

输入格式

第一行一个正整数 ,含义如上。

接下来 行,每行 个非负整数,这其中第 行第 列上的数字表示矩阵 中第 行第 列的值。

输出格式

唯一一行一个整数,表示矩阵的行列式对 取模后的值,如果该行列式存在;

否则输出

样例

样例输入 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

Arknights!

数据范围与提示

对于 的测试数据,