题目描述
小 ε 和小 ω 是两个关系很好的女孩子,理所当然地,她们想要编织许多共同的回忆。
小 ω 喜欢画画,因此,她理所当然地想要和小 ε 一起在一张 n×n 的网格图上作画。
理所当然地,画纸一开始是蓝色的,而小 ε 和小 ω 想要将一些格子涂上绚丽的颜色。小 ε 拿着粉色的画笔,而小 ω 拿着白色的画笔。
为了兼顾画面的美观性与简洁性,小 ε 想要在每行中选择 1 个格子涂上粉色,而小 ω 想要在每行中选择 2 个格子涂上白色。由于颜色的重叠会使得图案显得杂乱,理所当然地,她们选择的格子需要两两不同。
作为一名优秀的画家,小 ω 想要在创作的同时保持画面的平衡性。因此,她想要在绘画结束后,每列中的白色格子数量相同。
现在,小 ε 已经完成了画作前一部分的创作。对于任意 1≤i≤n,她选择了第 i 行的第 pi(1≤pi≤n) 个格子涂上了粉色。现在,小 ω 理所当然地想要求出她有多少种上色方式完成画作的后半部分,使得最终的画作符合以上的所有要求。
由于答案可能很大,你只需要输出其对 998244353 取模后的结果。
输入格式
本题有多组测试数据。输入的第一行两个整数 c,T 表示测试点编号和测试数据组数,特别的,在样例输入中,c=0。
对于每组测试数据:
- 第一行一个正整数 n,表示画布的尺寸;
- 第二行 n 个正整数 p1,p2,⋯,pn,其中第 i 个整数 pi(1≤pi≤n) 表示第 i 行中小 ε 染色过的格子所在列编号。
输出格式
对于每组测试数据,输出一行一个非负整数表示答案。
样例输入
0 4
1
1
2
1 2
3
1 2 3
4
2 3 4 1
样例输出
0
0
1
9
样例解释
该组样例中共包含 4 组测试数据。
- 对于第 1 组和第 2 组测试数据,可以证明小 ω 不存在符合条件的染色方案;
- 对于第 3 组测试数据,唯一一种可能的方案为小 ω 将 (1,2),(1,3),(2,1),(2,3),(3,1),(3,2) 所代表的格子染上颜色,其中 (x,y) 代表位于第 x 行第 y 列的格子;
- 对于第 4 组测试数据,一种可能的方案为小 ω 选择 (1,1),(1,3),(2,1),(2,4),(3,2),(3,4),(4,2),(4,3) 这些格子染白。
数据范围与提示
对于所有测试数据:
- 1≤T≤10;
- 1≤n≤500;
- 对于任意 1≤i≤n,1≤pi≤n。
各测试点的具体限制见下表:
| 测试点编号 |
n≤ |
特殊性质 |
| 1∼3 |
8 |
无 |
| 4∼5 |
12 |
| 6∼7 |
20 |
| 8 |
50 |
| 9∼10 |
100 |
| 11∼12 |
500 |
A |
| 13∼15 |
B |
| 16∼17 |
C |
| 18∼19 |
D |
| 20∼21 |
300 |
无 |
| 22∼25 |
500 |
特殊性质 A:保证 p1,p2,⋯,pn 互不相同;
特殊性质 B:p1,p2,⋯,pn 中不同数字的种类数不超过 8;
特殊性质 C:对于每个 1≤x≤n,满足 pi=x 的 i(1≤i≤n) 的个数不超过 2;
特殊性质 D:记 f(x) 为满足 pi=x 的 i 的数量,则满足 f(x)≥3 的 x(1≤x≤n) 数量不超过 10。