美丽矩阵的稀有度

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

一个 $n\times n$ 的矩阵是美丽的，当且仅当：

• 每个元素都是 $1$ 到 $n$ 之间的整数；
• 每一行的元素互不相同；
• 任意两个竖直相邻的元素不同。

把所有 $n\times n$ 的美丽矩阵按行优先的字典序从小到大排列。一个矩阵的稀有度是它在这个序列中的下标，其中最小矩阵的下标为 $0$。

给定一个美丽矩阵 $a$，求它的稀有度对 $998244353$ 取模的结果。

输入格式

第一行一个整数 $n$。

随后 $n$ 行，每行 $n$ 个整数，描述矩阵 $a$。

输出格式

输出一个整数，表示矩阵的稀有度模 $998244353$。

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

数据范围

对于所有数据，$1\le n\le2000$，输入保证 $a$ 是美丽矩阵。

每个测试点独立计分。