D. Flag performance
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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$$$.

Input

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$$$.
Output

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$$$.

Examples
Input
4 2 1
4 1 2 3
Output
0
Input
4 3 1
4 1 2 3
Output
16
Input
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
Output
310571736
0
745108126
996135367
597596468
745108126
0
0
310571736
0
Note

Sample Explanation 1

It is impossible to sort the flags with two exchanges.