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

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

Опис схеми маршрутизації складається з множини \(S\) спрямованих шляхів від посилачів до одержувачів таких, що ніякі з цих шляхів не маю спільну кінцеву точку. Тобто шляхи з'єднують різних посилачів із різними одержувачами. Шлях від посилача \(s\) до одержувача \(r\) може бути описаний як послідовність вершин \(s=v_0\to v_1 \to v_2\to \cdots \to v_e=r\) Такі направлені ребра \(v_i\to v_{i+1}\) існують для всіх \(0\le i<e\). Одна вершина може з'явитися більш ніж один раз на тому самому шляху.

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

Кожне введення містить \(T\) (\(1\le T\le 20\)) тестів, які потрібно вирішувати незалежно. Гарантується, що сума \(N^2\) всіх тестів не перевищить \(2\cdot 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 \) одиниць нижче головної діагоналі.

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

Формат вихідних даних

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

Приклад вхідних даних

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\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

5 1
SS.RR
00101
00100
10010
00000
00000

6 2
S....R
001000
000100
010001
000010
001000
000000

Приклад вихідних даних

3
1

Для першого тесту, ребра \(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\).

Приклад вхідних даних

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

Це додаткові невеликі тести.

ОЦІНЮВАННЯ:

• У тестах 4-5 \(N\le 6\).
• У тестах 6-7 \(K=0\).
• У тестах 8-12 \(K=1\).
• У тестах 13-24 \(K=2\).