Выступление с флагами

Вы отвечаете за команду в новом виде спорта — упорядоченной гимнастике. В этой дисциплине участвуют команды из $n$ человек. Каждый участник одет в костюм определённого цвета (число от $1$ до $n$) и держит флаг, также окрашенный в уникальный цвет, пронумерованный от $1$ до $n$. Выступление состоит ровно из $k$ шагов. На каждом шаге два участника обмениваются флагами. Начальная расстановка флагов может быть выбрана произвольно. Единственное ограничение состоит в том, что в конце выступления каждый участник должен держать флаг, цвет которого соответствует цвету его костюма.

Как капитану команды, Вам хотелось бы сделать выступление максимально непредсказуемым. Вы рассматриваете $t$ возможных начальных расстановок флагов среди участников и хотите узнать: сколько существует способов выполнить выступление для каждой из начальных расстановок?

Для каждой из данных $t$ начальных расстановок определите количество возможных способов выполнить выступление. Так как ответы могут быть очень большими, выведите их по модулю простого числа $10^9+7$.

Giriş verilənləri

Первая строка содержит три числа, разделённые пробелом: $n(2\le n\le 30)$, $k(1\le k\le 50)$ и $t(1\le t\le 10^4)$. Далее следуют $t$ строк, каждая из которых содержит $n$ различных целых чисел $c_{i,1},c_{i,2},...,c_{i,n}$, представляющих $i$-ю начальную конфигурацию флагов среди участников команды. Здесь $c_{i,j}$ — это номер цвета флага, который изначально находится у участника с цветом костюма $j$.

Çıxış verilənləri

Выведите $t$ строк. $i$-я из таких строк должна содержать одно число: количество возможных последовательностей обменов, которые начинаются с $i$-й конфигурации и удовлетворяют указанным условиям, по модулю $10^9+7$.

Nümunələr

Пример 1. Невозможно упорядочить флаги с помощью двух обменов.