P13795 [SWERC 2023] Flag performance

:::align{center}  ::: 你负责一支“有序体操”队伍。这项新兴运动需要 $N$ 名队员。每位队员穿着不同颜色的服装（编号为 $1$ 到 $N$），并持有一面彩旗。旗帜的颜色也各不相同，同样编号为 $1$ 到 $N$。一次表演恰好包含 $K$ 个步骤，每一步有两名队员交换手中的旗帜。你可以自由选择旗帜的初始分配方式。唯一的要求是，在表演结束时，每位队员手中必须持有与自己服装颜色相同编号的旗帜。 作为队长，你希望表演尽可能不可预测。你考虑了 $T$ 种可能的旗帜初始分配方式，并想知道：对于每种初始分配，队伍有多少种完成任务的方式？ 对于给定的 $T$ 种初始分配方式，请计算每种情况下可能的表演方式数。由于答案可能非常大，请对质数 $1~000~000~007$ 取模后输出。

每行由若干空格分隔的整数组成。第一行包含 $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$。

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

**样例解释 1** 用两次交换无法将旗帜归位。 由 ChatGPT 4.1 翻译