Схеми маршрутизації

Обмеження на час виконання 1 секунда

Обмеження на використання пам'яті 128 мегабайтів

Розгляньмо мережу з $n$ вершин, позначених числами від $1$ до $n$ . Кожна вершина може бути відправником, отримувачем або ні тим, ні іншим. Кількість відправників $S$ дорівнює кількості отримувачів $(S \geq 1)$ .

Зв'язки між вершинами в мережі описуються списком спрямованих ребер у вигляді $i \to j$ , що означає, що вершина $i$ може передавати інформацію вершині $j$ . Всі ці ребра задовольняють умову $i < j$ , за винятком $k$ ребер, які задовольняють умову $i > j$ . Циклів (ребер виду $i \to i$ ) немає.

Схема маршрутизації складається з множини $S$ спрямованих шляхів від відправників до отримувачів, таких, що жодні два з цих шляхів не мають спільної кінцевої точки. Тобто шляхи з'єднують різних відправників з різними отримувачами. Шлях від відправника $s$ до отримувача $r$ може бути описаний як послідовність вершин

s = v_{0} \to v_{1} \to v_{2} \to ... \to v_{e} = r

така, що спрямовані ребра $v_{i} \to v_{i + 1}$ існують для всіх $0 \leq i < e$ . Одна вершина може з'явитися більше ніж один раз в одному і тому ж шляху.

Порахуйте кількість різних схем маршрутизації, таких, що кожне спрямоване ребро проходиться рівно один раз. Оскільки відповідь може бути дуже великою, виводьте її за модулем $1 0^{9} + 7$ . Гарантується, що існує хоча б одна схема маршрутизації, що задовольняє обмеженням.

Кожен набір вхідних даних містить $t$ тестів. Гарантується, що сума $n^{2}$ всіх тестів не перевищить $2 \cdot 1 0^{4}$ .

Вхідні дані

Перша рядок містить кількість тестів $t (1 \leq t \leq 20)$ .

Перша рядок кожного тесту містить цілі числа $n (2 \leq n \leq 100)$ і $k (0 \leq k \leq 2)$ . Зазначимо, що $S$ не визначається явно у вводі.

Друга рядок кожного тесту містить рядок довжини $n$ . $i$ -ий символ рядка дорівнює $S$ , якщо $i$ -а вершина відправник, $R$ — якщо $i$ -а вершина отримувач, $.$ — якщо $i$ -а вершина ні те, ні інше. Кількості символів $R$ і $S$ рівні. Є хоча б один символ $S$ .

Кожна з $n$ наступних рядків тесту містить бітовий рядок з $n$ нулів і одиниць. $j$ -ий біт в $i$ -ій рядку дорівнює $1$ , якщо існує спрямоване ребро від вершини $i$ до вершини $j$ , і $0$ в іншому випадку. Оскільки петель немає, на головній діагоналі всі нулі. Більше того, є рівно $k$ одиниць нижче головної діагоналі.

Послідовні тести розділені порожніми рядками для читабельності.

Вихідні дані

Для кожного тесту виведіть кількість схем маршрутизації таких, що кожне ребро проходиться рівно один раз, за модулем $1 0^{9} + 7$ . Гарантується, що існує хоча б одна валідна схема маршрутизації.

Приклади

Приклад 1. Для першого тесту ребра мають вигляд:

1 \to 3, 2 \to 3, 3 \to 4, 3 \to 5, 4 \to 6, 5 \to 6, 6 \to 7, 6 \to 8

Існують чотири схеми маршрутизації:

1 \to 3 \to 4 \to 6 \to 7, 2 \to 3 \to 5 \to 6 \to 8 1 \to 3 \to 5 \to 6 \to 7, 2 \to 3 \to 4 \to 6 \to 8 1 \to 3 \to 4 \to 6 \to 8, 2 \to 3 \to 5 \to 6 \to 7 1 \to 3 \to 5 \to 6 \to 8, 2 \to 3 \to 4 \to 6 \to 7

Для другого тесту ребра мають вигляд:

1 \to 4, 2 \to 4, 3 \to 4, 4 \to 5, 4 \to 6, 4 \to 7, 8 \to 10, 9 \to 10, 10 \to 11, 10 \to 12

Одна з можливих схем маршрутизації:

1 \to 4 \to 5 2 \to 4 \to 7 3 \to 4 \to 6 8 \to 10 \to 12 9 \to 10 \to 11

У загальному випадку відправники ${1, 2, 3}$ можуть маршрутизуватися деякою перестановкою отримувачів ${5, 6, 7}$ , і відправники ${8, 9}$ можуть маршрутизуватися деякою перестановкою отримувачів ${11, 12}$ даючи відповідь $6 \cdot 2 = 12$ .

Приклад 2. Для першого тесту ребра мають вигляд:

1 \to 3, 1 \to 5, 2 \to 3, 3 \to 1, 3 \to 4

Існують три схеми маршрутизації:

1 \to 3 \to 1 \to 5, 2 \to 3 \to 4 1 \to 3 \to 4, 2 \to 3 \to 1 \to 5 1 \to 5, 2 \to 3 \to 1 \to 3 \to 4

Для другого тесту ребра мають вигляд:

1 \to 3, 2 \to 4, 3 \to 2, 3 \to 6, 4 \to 5, 5 \to 3

Існує тільки одна схема маршрутизації:

1 \to 3 \to 2 \to 4 \to 5 \to 3 \to 6

Вхідні дані #1

Відповідь #1

Вхідні дані #2

Відповідь #2

Вхідні дані #3

Відповідь #3

Відправки 6

Коефіцієнт прийняття 83%