← 返回题目列表

Codeforces · 1085/G

G. 美丽的矩阵

中文机器翻译题面 查看原题

Petya 收集美丽的矩阵。

大小为 $$$n \times n$$$ 的矩阵很漂亮,如果:

- 矩阵的所有元素都是 $$$1$$$ 和 $$$n$$$ 之间的整数;
- 对于矩阵的每一行,该行的所有元素都不同;
- 对于每对垂直相邻的元素,这些元素都是不同的。

今天 Petya 买了一个漂亮的矩阵 $$$a$$$,大小为 $$$n \times n$$$,现在他想确定它的稀有度。

矩阵的稀有度是其在大小为 $$$n \times n$$$ 的美丽矩阵列表中的索引,按字典顺序排序。矩阵比较是逐行进行的。 (字典顺序最小矩阵的索引为零)。

由于美丽矩阵的数量可能很大,Petya 希望您计算矩阵 $$$a$$$ 模 $$$998\,244\,353$$$ 的稀有度。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2000$$$) — $$$a$$$ 中的行数和列数。

接下来的 $$$n$$$ 行包含 $$$n$$$ 整数 $$$a_{i,j}$$$ ($$$1 \le a_{i,j} \le n$$$) — $$$a$$$ 的元素。

保证 $$$a$$$ 是一个漂亮的矩阵。

输出

打印一个整数 — 矩阵 $$$a$$$ 的稀有度,以 $$$998\,244\,353$$$ 为模。

示例

输入 #1

2
2 1
1 2

输出 #1

1

输入 #2

3
1 2 3
2 3 1
3 1 2

输出 #2

1

输入 #3

3
1 2 3
3 1 2
2 3 1

输出 #3

3

注意

只有 $$$2$$$ 大小为 $$$2 \times 2$$$ 的漂亮矩阵:

有第一个 $$$5$$$ 美丽的矩阵,大小为 $$$3 \times 3$$$ 按字典顺序排列: