5C.生成排列（perm）

对于一个 $1,2,\ldots, n$ 的排列 $p=[p_1,p_2,\ldots,p_n]$，考虑如下操作：

• 初始化一个序列 $q=[1,2,\ldots,n]$；
• 对于每个 $1\le i\le n$，依次 交换 $q_{p_i}$ 与 $q_{p_i+1}$。特别地，当 $p_i=n$ 时，交换 $q_n$ 与 $q_1$；
• 称最终的序列 $q$ 为 $p$ 的 生成排列。

给定某个序列 $r=[r_1,r_2,\ldots,r_n]$，计算有多少个初始排列 $p$ 可能以 $r$ 作为其生成排列。由于答案可能很大，你只需要输出其对 $998\,244\,353$ 取模的值。

从文件 perm.in 中读入数据。

本题包含多组测试数据。输入的第一行包含两个正整数 $c,t$，分别表示测试点编号以及测试数据组数。$c=0$ 表示该测试点为样例。

对于每组测试数据：

• 第一行包含一个正整数 $n$，表示排列长度；
• 第二行包含 $n$ 个互不相同的正整数 $r_1,r_2,\ldots,r_n$。

输出到文件 perm.out。

对于每组测试数据，输出一行一个整数，表示符合条件的排列 $p$ 的个数对 $998\,244\,353$ 取模的结果。

0 3
2
1 2
5
3 1 2 5 4
8
1 7 2 8 5 3 6 4

2
3
0

对于第一组测试数据，所有长度为 $2$ 的排列均以 $[1,2]$ 为生成排列，所以答案为 $2$。

对于第二组测试数据，所有符合条件的初始排列 $p$ 为 $[3,2,1,4,5]$、$[3,2,4,1,5]$ 和 $[3,4,2,1,5]$。

对于第三组测试数据，可以证明，不存在符合要求的初始排列。

该样例满足测试点 $4,5$ 的限制条件。

该样例满足测试点 $11\sim14$ 的限制条件。

该样例满足测试点 $15,16$ 的限制条件。

该样例满足测试点 $20$ 的限制条件。

对于全部测试数据，保证：

• $1\le t \le 5$；
• $1\le n\le 10^3$；
• $r_1,r_2,\ldots,r_n$ 是 $1,2,\ldots ,n$ 的一个排列。

特殊性质：存在至少一个 $1\le i\le n$，使得 $p_i=i$。