UOJ Logo Universal Online Judge

UOJ

#154. 【UR #10】列队

统计

picks 博士通过实验成功地得到了排列 $A$,并根据这个回到了正确的过去。他在金星凌日之前顺利地与丘比签订了契约,成为了一名马猴烧酒。

picks 博士可以使用魔法召唤很多很多的猴子与他一起战斗,但是当猴子的数目 $n$ 太大的时候,训练猴子就变成了一个繁重的任务。

历经千辛万苦,猴子们终于学会了按照顺序排成一排。为了进一步训练,picks 博士打算设定一系列的指令,每一条指令 $i$ 的效果都可以用一个 $1$ 到 $n$ 的排列 $P_i$ 表示,picks 博士希望喊出这条指令之后,猴子们能够自行交换顺序,使得之前排在第 $j$ 个的猴子在交换结束后排在第 $P_{i,j}$的位置。

因为实战时争分夺秒,他认为一个完善的指令系统必须满足如下的条件:

  1. 对于任意的两条指令 $i$ 和 $j$ ($i$ 和 $j$ 可以相同),在指令系统中一定存在一条指令 $k$,使得依次喊出第 $i$ 条指令和第 $j$ 条指令的效果和直接喊出第 $k$ 条指令的效果是一样的。picks 博士认为这样可以提高战场上发号施令的效率。
  2. 任意两条不同指令 $i$ 和 $j$ 的效果是不同的。picks 博士认为这样可以避免指令系统过于臃肿。

现在 picks 博士已经完成了对指令系统大致的构思。具体来说,他已经得到了一个整数 $m$ 以及一个 $m \times m$ 的表格 $B$。整数 $m$ 表示指令系统中指令的数量,$B_{i,j}$ 表示依次喊出第 $i$ 条指令和第 $j$ 条指令的效果和直接喊出第 $B_{i,j}$ 条指令的效果是一样的。

现在 picks 博士想要根据 $m$ 和 $B$ 来得到一个完善的指令系统。然而他发现这样的指令系统有很多,这引起了他的兴趣,他想要你帮他统计满足条件的完善的指令系统究竟有多少个。

两个指令系统是不同的当且仅当至少存在一个 $i$ 使得两个指令系统中的第 $i$ 条指令不同。

不保证一定存在满足条件的完善的指令系统,毕竟聪慧过人的马猴烧酒 picks 博士也有搞错的时候嘛。

输入格式

第一行一个正整数 $T$,表示数据组数。

对于每组数据,第一行是两个正整数 $n$ 和 $m$,表示猴子的数量以及指令系统的指令数量。

接下来 $m$ 行每行 $m$ 个正整数 $B_{i,j}$,表示依次喊出第 $i$ 条指令和第 $j$ 条指令的效果和直接喊出第 $B_{i,j}$ 条指令的效果是一样的。保证有$1 \leq B_{i,j} \leq m$。

输出格式

对于每组数据输出一个整数表示答案。

答案可能很大,你只需要输出答案对 $998244353(7\times 17 \times 2^{23}+1$,一个质数$)$ 取模后的结果。

样例一

input

1
3 2
1 2
2 1

output

3

explanation

可能的三种指令系统为:

  1. 第一个指令为排列 $1\ 2\ 3$,第二个指令为排列 $1\ 3\ 2$。
  2. 第一个指令为排列 $1\ 2\ 3$,第二个指令为排列 $2\ 1\ 3$。
  3. 第一个指令为排列 $1\ 2\ 3$,第二个指令为排列 $3\ 2\ 1$。

样例二

见样例数据下载。

限制与约定

测试点编号$m$ 的规模$n$ 的规模其他
1$m \leq 4$$n \leq 5$
2
3$m \leq 30$$n \leq 1000$$B_{i,j} \equiv i+j-1 \pmod{m}$
4
5$m \leq 16$
6
7
8$m \leq 30$
9
10

对于所有数据,保证有 $T \leq 10$。

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载