Рассмотрим сеть из N (2≤N≤100) вершин, помеченных 1…N. Каждая вершина обозначена как посылатель, получатель или ни то, ни другое. Количество посылателей S равно количеству получателей (S≥1).
Связи между двумя вершинами в сети могут быть описаны как список направленных ребер каждое в виде i→j, обозначающее, что вершина i может передать информацию вершине j. Интересно, что все эти рёбра удовлетворяют свойству i<j, кроме K которые удовлетворяют свойству i>j (0≤K≤2). Нет циклов (ребер вида i→i).
Описание схемы маршрутизации состоит из множества S направленных путей от посылателей к получателям таких, что никакие два из этих путей не имею общую конечную точку. То есть пути соединяют различных посылателей с различными получателями. Путь от посылателя s к получателю r может быть описан как последовательность вершин
s=v0→v1→v2→?→ve=r
такая что направленные ребра vi→vi+1 существуют для всех 0≤i<e. Одна вершина может появиться более чем один раз в одном и том же пути.
Посчитайте количество различных схем маршрутизации, таких, что каждое направленное ребро проходится ровно один раз. Поскольку ответ может быть очень большим, выводите его по модулю 10
9+7. Гарантируется, что существует хотя бы одна схема маршрутизации, удовлетворяющая ограничениям.
Каждый ввод содержит T (1≤T≤20) тестов, которые требуется решать независимо. Гарантируется, что сумма N
2 всех тестов не превысит 2⋅10
4.
Входные данные:
Первая строка содержит T, количество тестов.
Первая строка каждого теста содержит целые числа N и K. Заметим, что S не определяется явно во вводе.
Вторая строка каждого теста содержит строку длины N. i-ый символ строки равен S если i-ая вершина посылатель, R - если i-ая вершина - получатель, . - если i-ая вершина - ни то, ни другое. Количества символов R и S равны. Есть хотя бы один символ S.
Каждая из N последующих строк теста содержит битовую строку из N нулей и единиц. j-ый бит в i-ой строке равен 1, если существует направленное ребро от вершины i к вершине j, и 0 в протвном случае. Поскольку петель нет, на главной диагонали все нули. Более того имеется ровно K единиц ниже главной диагонали.
Последовательные тесты разделены пустыми строками для читабельности.
Выходные данные:
Для каждого теста выведите количество схем маршрутизации таких, что каждое ребро проходится ровно один раз, по модулю 109+7. Гарантируется, что существует хотя бы одна валидная схема маршрутизации.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснение |
| 1 |
2
8 0
SS....RR
00100000
00100000
00011000
00000100
00000100
00000011
00000000
00000000
13 0
SSS.RRRSS.RR.
0001000000000
0001000000000
0001000000000
0000111000000
0000000000000
0000000000000
0000000000000
0000000001000
0000000001000
0000000000110
0000000000000
0000000000000
0000000000000 |
4
12 |
Для первого теста ребра таковы 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}, и посылатели {8,9} могут маршрутизироваться некоторой перестановкой получателей {11,12} давая ответ 6 ⋅ 2=12.
|
| 2 |
2
5 1
SS.RR
00101
00100
10010
00000
00000
6 2
S....R
001000
000100
010001
000010
001000
000000 |
3
1 |
Для первого теста, ребра 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. |
| 3 |
5
3 2
RS.
010
101
100
4 2
.R.S
0100
0010
1000
0100
4 2
.SR.
0000
0011
0100
0010
5 2
.SSRR
01000
10101
01010
00000
00000
6 2
SS..RR
001010
000010
000010
000010
100101
000000 |
2
1
2
6
24 |
|