Рассмотрим сеть из вершин, помеченных . Каждая вершина обозначена как посылатель, получатель или ни то, ни другое. Количество посылателей равно количеству получателей .
Связи между двумя вершинами в сети могут быть описаны как список направленных ребер каждое в виде , обозначающее, что вершина может передать информацию вершине . Интересно, что все эти рёбра удовлетворяют свойству , кроме ребер, которые удовлетворяют свойству . Нет циклов (ребер вида ).
Описание схемы маршрутизации состоит из множества направленных путей от посылателей к получателям таких, что никакие два из этих путей не имею общую конечную точку. То есть пути соединяют различных посылателей с различными получателями. Путь от посылателя к получателю может быть описан как последовательность вершин
такая что направленные ребра существуют для всех . Одна вершина может появиться более чем один раз в одном и том же пути.
Посчитайте количество различных схем маршрутизации, таких, что каждое направленное ребро проходится ровно один раз. Поскольку ответ может быть очень большим, выводите его по модулю . Гарантируется, что существует хотя бы одна схема маршрутизации, удовлетворяющая ограничениям.
Каждый набор входных данных содержит тестов. Гарантируется, что сумма всех тестов не превысит .
Первая строка содержит количество тестов .
Первая строка каждого теста содержит целые числа и . Заметим, что не определяется явно во вводе.
Вторая строка каждого теста содержит строку длины . -ый символ строки равен если -ая вершина посылатель, — если -ая вершина получатель, — если -ая вершина ни то, ни другое. Количества символов и равны. Есть хотя бы один символ .
Каждая из последующих строк теста содержит битовую строку из нулей и единиц. -ый бит в -ой строке равен , если существует направленное ребро от вершины к вершине , и в противном случае. Поскольку петель нет, на главной диагонали все нули. Более того имеется ровно единиц ниже главной диагонали.
Последовательные тесты разделены пустыми строками для читабельности.
Для каждого теста выведите количество схем маршрутизации таких, что каждое ребро проходится ровно один раз, по модулю . Гарантируется, что существует хотя бы одна валидная схема маршрутизации.
Пример 1. Для первого теста ребра ребра имеют вид:
Имеются четыре схемы маршрутизации:
Для второго теста ребра имеют вид:
Одна из возможных схем маршрутизации:
В общем случае посылатели могут маршрутизироваться некоторой перестановкой получателей , и посылатели могут маршрутизироваться некоторой перестановкой получателей давая ответ .
Пример 2. Для первого теста ребра имеют вид:
Имеются три схемы маршрутизации:
Для второго теста ребра имеют вид:
Имеется только одна схема маршрутизации: