Схеми маршрутизації#11241
Увійти

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

1 секунда
128 мегабайтів
Дуже складна

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

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

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

s = v_0 → v_1 → v_2 → ... → v_e = r

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

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

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

Вхідні дані

Перший рядок містить кількість тестів t~(1 \le t \le 20).

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

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

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

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

Вихідні дані

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

Приклади

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

1 → 3, 2 → 3, 3 → 4, 3 → 5, 4 → 6, 5 → 6, 6 → 7, 6 → 8

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

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

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

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

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

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

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

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

1 → 3, 1 → 5, 2 → 3, 3 → 1, 3 → 4

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

1 → 3 → 1 → 5, 2 → 3 → 4 \\ 1 → 3 → 4, 2 → 3 → 1 → 5 \\ 1 → 5, 2 → 3 → 1 → 3 → 4

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

1 → 3, 2 → 4, 3 → 2, 3 → 6, 4 → 5, 5 → 3

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

1 → 3 → 2 → 4 → 5 → 3 → 6

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Приклад 3

Loading
Loading