Description

:::align{center}

:::

你负责一支“有序体操”队伍。这项新兴运动需要 $N$ 名队员。每位队员穿着不同颜色的服装（编号为 $1$ 到 $N$），并持有一面彩旗。旗帜的颜色也各不相同，同样编号为 $1$ 到 $N$。一次表演恰好包含 $K$ 个步骤，每一步有两名队员交换手中的旗帜。你可以自由选择旗帜的初始分配方式。唯一的要求是，在表演结束时，每位队员手中必须持有与自己服装颜色相同编号的旗帜。

作为队长，你希望表演尽可能不可预测。你考虑了 $T$ 种可能的旗帜初始分配方式，并想知道：对于每种初始分配，队伍有多少种完成任务的方式？

对于给定的 $T$ 种初始分配方式，请计算每种情况下可能的表演方式数。由于答案可能非常大，请对质数 $1~000~000~007$ 取模后输出。

Input Format

每行由若干空格分隔的整数组成。第一行包含 $N$、$K$ 和 $T$。接下来有 $T$ 行。第 $k$ 行包含 $N$ 个互不相同的整数 $c_{k,1}, c_{k,2}, \dots, c_{k,N}$，表示第 $k$ 种初始旗帜分配方式。其中 $c_{k,i}$ 表示服装颜色为 $i$ 的队员手中最初持有的旗帜编号。

数据范围

• $2 \leq N \leq 30$；
• $1 \leq K \leq 50$；
• $1 \leq T \leq 10~000$。

Output Format

输出应包含 $T$ 行。第 $k$ 行输出一个整数，表示从第 $k$ 种初始分配方式出发，满足要求的交换序列总数，对 $1~000~000~007$ 取模。

4 2 1
4 1 2 3

0

4 3 1
4 1 2 3

16

6 15 10
5 6 1 2 4 3
2 4 1 6 5 3
4 1 3 6 5 2
1 3 2 4 5 6
4 5 6 1 2 3
1 2 5 3 6 4
6 4 2 3 1 5
3 6 4 1 2 5
4 5 1 2 6 3
6 1 4 3 2 5

310571736
0
745108126
996135367
597596468
745108126
0
0
310571736
0

Hint

样例解释 1

用两次交换无法将旗帜归位。

由 ChatGPT 4.1 翻译