31485번 - 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 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$^th such line consists of $N$ distinct space-separated integers $c_{k,1}, c_{k,2}, \dots , c_{k,N},ドル representing the $k$^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$.

출력

The output should contain $T$ lines. The $k$^th such line should consist of a single number: the number of possible sequences of exchanges that start from the $k$^th configuration and satisfy the constraints listed above, modulo 1ドル,円 000,円 000,円 007$.

제한

• 2ドル \le N \le 30$
• 1ドル \le K \le 50$
• 1ドル \le T \le 10,円 000$

힌트