Рассмотрим сеть из n вершин, помеченных 1...n. Каждая вершина обозначена как посылатель, получатель или ни то, ни другое. Количество посылателей S равно количеству получателей (S≥1).
Связи между двумя вершинами в сети могут быть описаны как список направленных ребер каждое в виде i→j, обозначающее, что вершина i может передать информацию вершине j. Интересно, что все эти рёбра удовлетворяют свойству i<j, кроме k ребер, которые удовлетворяют свойству i>j. Нет циклов (ребер вида i→i).
Описание схемы маршрутизации состоит из множества S направленных путей от посылателей к получателям таких, что никакие два из этих путей не имею общую конечную точку. То есть пути соединяют различных посылателей с различными получателями. Путь от посылателя s к получателю r может быть описан как последовательность вершин
такая что направленные ребра vi→vi+1 существуют для всех 0≤i<e. Одна вершина может появиться более чем один раз в одном и том же пути.
Посчитайте количество различных схем маршрутизации, таких, что каждое направленное ребро проходится ровно один раз. Поскольку ответ может быть очень большим, выводите его по модулю 109+7. Гарантируется, что существует хотя бы одна схема маршрутизации, удовлетворяющая ограничениям.
Каждый набор входных данных содержит t тестов. Гарантируется, что сумма n2 всех тестов не превысит 2⋅104.
Первая строка содержит количество тестов t (1≤t≤20).
Первая строка каждого теста содержит целые числа n (2≤n≤100) и k (0≤k≤2). Заметим, что S не определяется явно во вводе.
Вторая строка каждого теста содержит строку длины n. i-ый символ строки равен S если i-ая вершина посылатель, R — если i-ая вершина получатель, . — если i-ая вершина ни то, ни другое. Количества символов R и S равны. Есть хотя бы один символ S.
Каждая из n последующих строк теста содержит битовую строку из n нулей и единиц. j-ый бит в i-ой строке равен 1, если существует направленное ребро от вершины i к вершине j, и 0 в противном случае. Поскольку петель нет, на главной диагонали все нули. Более того имеется ровно k единиц ниже главной диагонали.
Последовательные тесты разделены пустыми строками для читабельности.
Для каждого теста выведите количество схем маршрутизации таких, что каждое ребро проходится ровно один раз, по модулю 109+7. Гарантируется, что существует хотя бы одна валидная схема маршрутизации.
Пример 1. Для первого теста ребра ребра имеют вид:
Имеются четыре схемы маршрутизации:
Для второго теста ребра имеют вид:
Одна из возможных схем маршрутизации:
В общем случае посылатели {1,2,3} могут маршрутизироваться некоторой перестановкой получателей {5,6,7}, и посылатели {8,9} могут маршрутизироваться некоторой перестановкой получателей {11,12} давая ответ 6⋅2=12.
Пример 2. Для первого теста ребра имеют вид:
Имеются три схемы маршрутизации:
Для второго теста ребра имеют вид:
Имеется только одна схема маршрутизации: