题目描述

:::align{center}

:::

You are in charge of a team of sorted gymnastics. This new discipline involves teams of $N$ members. Each team member dresses with a different colour (a number from $1$ to $N$) and holds a coloured flag. Flags have unique colours, also numbered from $1$ to $N$. A performance consists of exactly $K$ steps. At each step, two members exchange their flags. You are free to choose the initial configuration of the flags. The only constraint is that, at the end of the performance, each participant must hold the flag corresponding to the colour of his outfit.

Being the team captain, you would like the performance to be as unpredictable as possible. You consider $T$ possible initial configurations of flags among the team members, and wonder: in how many ways can the team perform the task for each of these initial configurations?

For each of the given $T$ initial configurations, compute the number of possible ways to do the performance. As the answers may be very large, return them modulo the prime number $1~000~000~007$.

输入格式

Each line consists of space-separated integers. The first input line contains the numbers $N$, $K$, and $T$. Then follow $T$ lines. The $k^{\text{th}}$ such line consists of $N$ distinct space-separated integers $c_{k,1}, c_{k,2}, \dots, c_{k,N}$, representing the $k^{\text{th}}$ initial configuration of flags among team members. Here, $c_{k,i}$ is colour number of the flag initially in the hands of the team member whose outfit colour is $i$.

Limits

• $2 \leq N \leq 30$;
• $1 \leq K \leq 50$.
• $1 \leq T \leq 10~000$.

输出格式

The output should contain $T$ lines. The $k^{\text{th}}$ such line should consist of a single number: the number of possible sequences of exchanges that start from the $k^{\text{th}}$ configuration and satisfy the constraints listed above, modulo $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

提示

Sample Explanation 1

It is impossible to sort the flags with two exchanges.