라우팅 방식

$N$개($2 \le N \le 100$)의 노드가 $1$부터 $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=v_0 \to v_1 \to v_2 \to \cdots \to v_e=r$은 각 $0 \le i < e$에 대해 간선 $v_i \to v_{i+1}$이 존재할 때 유효하다. 한 경로 안에서 같은 노드가 여러 번 나올 수 있다.

모든 방향 간선을 정확히 한 번씩 지나가는 라우팅 방식의 수를 구하라. 답이 매우 클 수 있으므로 $10^9+7$로 나눈 나머지를 출력한다. 각 테스트 케이스마다 조건을 만족하는 라우팅 방식이 적어도 하나 있음이 보장된다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다 ($1 \le T \le 20$). 각 테스트 케이스는 독립적으로 푼다. 모든 테스트 케이스에 대한 $N^2$의 합은 $2 \cdot 10^4$을 넘지 않는다.

각 테스트 케이스의 첫 줄에는 정수 $N$과 $K$가 주어진다. $S$는 입력에 따로 주어지지 않는다.

둘째 줄에는 길이 $N$의 문자열이 주어진다. $i$번째 문자가 S이면 노드 $i$는 송신자, R이면 수신자, .이면 둘 다 아니다. 문자열의 R 개수는 S 개수와 같으며 S는 적어도 하나 있다.

이어지는 $N$개의 줄에는 각각 길이 $N$의 이진 문자열이 주어진다. $i$번째 줄의 $j$번째 비트가 1이면 노드 $i$에서 노드 $j$로 가는 간선이 있고, 0이면 없다. 대각선은 모두 0이다. 대각선 아래쪽에 있는 1은 정확히 $K$개이다.

각 테스트 케이스마다 모든 간선을 정확히 한 번씩 지나가는 라우팅 방식의 수를 $10^9+7$로 나눈 나머지를 한 줄에 출력한다.