你负责管理一支“排序体操”队。这项新运动涉及 $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$ 的队员最初持有的旗帜颜色编号。

输出格式

输出应包含 $T$ 行。第 $k$ 行应包含一个数字：从第 $k$ 种配置开始并满足上述限制的可能交换序列的数量，对 $1\,000\,000\,007$ 取模。

数据范围

• $2 \leqslant N \leqslant 30$
• $1 \leqslant K \leqslant 50$
• $1 \leqslant T \leqslant 10\,000$

样例

样例输入 1

4 2 1
4 1 2 3

样例输出 1

0

说明 1

无法通过两次交换对旗帜进行排序。

样例输入 2

4 3 1
4 1 2 3

样例输出 2

16

样例输入 3

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

样例输出 3

310571736
0
745108126
996135367
597596468
745108126
0
0
310571736
0