Виступ із прапорами#11748
Ви відповідаєте за команду в новому виді спорту - впорядкованій гімнастиці. У цій дисципліні беруть участь команди із осіб. Кожен учасник одягнений у костюм певного кольору (число від до ) і тримає прапор, також пофарбований в унікальний колір, пронумерований від до . Виступ складається рівно з кроків. На кожному кроці два учасники обмінюються прапорами. Початкова розстановка прапорів може бути обрана довільно. Єдине обмеження полягає в тому, що наприкінці виступу кожен учасник має тримати прапор, колір якого відповідає кольору його костюма.
Як капітанові команди Вам хотілось би зробити виступ максимально непередбачуваним. Ви розглядаєте можливих початкових розстановок прапорів серед учасників і хочете дізнатися: скільки існує способів виконати виступ для кожної з початкових розстановок?
Для кожної з початкових розстановок визначте кількість можливих способів виконати виступ. Оскільки відповіді можуть бути дуже великими, виведіть їх за модулем простого числа 10^9 + 7.
Перший рядок містить три числа, розділені пробілом: n~(2 \le n \le 30), k~(1 \le k \le 50) і t~(1 \le t \le 10^4).
Далі йдуть рядків, кожен із яких містить різних цілих чисел c_{i,1}, c_{i,2}, ..., c_{i,n}, що представляють -ю початкову конфігурацію прапорів серед учасників команди.
c_{i,j} — це номер кольору прапора, який початково знаходиться в учасника з кольором костюма .
Виведіть рядків.
-ий рядок повинен містити одне число: кількість можливих послідовностей обмінів, які починаються з -ї конфігурації та задовольняють зазначені умови, за модулем 10^9 + 7.
Приклад 1. Неможливо впорядкувати прапори за допомогою двох обмінів.
Приклад 1
Приклад 2
Приклад 3