Рассмотрим сеть из n вершин, помеченных 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. Одна вершина может появиться более чем один раз в одном и том же пути.

Посчитайте количество различных схем маршрутизации, таких, что каждое направленное ребро проходится ровно один раз. Поскольку ответ может быть очень большим, выводите его по модулю 109 + 7. Гарантируется, что существует хотя бы одна схема маршрутизации, удовлетворяющая ограничениям.

Каждый ввод содержит t тестов. Гарантируется, что сумма n2 всех тестов не превысит 2 * 104.

Входные данные

Первая строка содержит количество тестов t (1 ≤ t ≤ 20).

Первая строка каждого теста содержит целые числа n (2 ≤ n ≤ 100) и k. Заметим, что S не определяется явно во вводе.

Вторая строка каждого теста содержит строку длины n. i-ый символ строки равен S если i-ая вершина посылатель, R - если i-ая вершина получатель, . - если i-ая вершина ни то, ни другое. Количества символов R и S равны. Есть хотя бы один символ S.

Каждая из n последующих строк теста содержит битовую строку из n нулей и единиц. j-ый бит в i-ой строке равен 1, если существует направленное ребро от вершины i к вершине j, и 0 в протвном случае. Поскольку петель нет, на главной диагонали все нули. Более того имеется ровно k единиц ниже главной диагонали.

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

Выходные данные

Для каждого теста выведите количество схем маршрутизации таких, что каждое ребро проходится ровно один раз, по модулю 109 + 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}, и посылатели {8, 9} могут маршрутизироваться некоторой перестановкой получателей {11, 12} давая ответ 6 * 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.