Flag performance

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 $10^9+7$.

Input

Each line consists of space-separated integers. The first line contains the numbers $n(2\le n\le 30),k(1\le k\le 50)$, and $t(1\le t\le 10^4)$. Then follow $t$ lines. The $i$-th such line consists of $n$ distinct integers $c_{i,1},c_{i,2},...,c_{i,n}$, representing the $i$-th initial configuration of flags among team members. Here, $c_{i,j}$ is colour number of the flag initially in the hands of the team member whose outfit colour is $j$.

Output

Print $t$ lines. The $i$-th such line should consist of a single number: the number of possible sequences of exchanges that start from the $i$-th configuration and satisfy the constraints listed above, modulo $10^9+7$.

Examples

Sample 1. It is impossible to sort the flags with two exchanges.