Background

线性代数大师今天又讲课了！线性代数大师高先生不仅讲课水平非常之高，而且因为其生动的描述和幽默的比喻深受大家喜爱。但是锐哥从开始上课的第二分钟起就一直 在玩《明日方舟》，因为这个游戏真的很好玩。

现在他被大师抽中回答一个问题。

Description

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

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

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

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

Format

Input

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

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

Output

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

否则输出 $Arknights!$ 。

Samples1

3
1 2 3
0 4 5
0 0 6

24

Samples2

3
1 0 0
2 3 0
4 5 6

18

Samples3

3
1 2 3
4 5 6
7 8 9

Arknights!

Limitation

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