패턴 매칭

Rikka에게 소문자 영어 알파벳으로 이루어진 $n$개의 집합 $S_1, S_2, \ldots, S_n$이 있다. 길이 $m$인 패턴 $p_1 p_2 \ldots p_m$이 집합들과 매칭된다는 것은, 다음 조건을 모두 만족하는 인덱스 $i$가 존재한다는 뜻이다: $p_1 \in S_i$, $p_2 \in S_{i+1}$, $\ldots$, $p_m \in S_{i+m-1}$.

처음에는 모든 집합이 비어 있다. Rikka는 집합에 적용할 연산을 여럿 준비했다. 각 연산은 "집합 $i$에 문자 $c$를 추가한다" 형태이다. 매 라운드마다 Rikka는 연산 하나를 같은 확률로 골라 적용한다. 같은 연산이 여러 번 골라질 수도 있다.

패턴이 집합들과 매칭될 때까지 걸리는 라운드 수의 기댓값을 구하라.

첫 줄에 테스트 케이스 수 $T$가 주어진다 ($1 \le T \le 5$).

각 테스트 케이스의 첫 줄에는 정수 $n$, $m$이 주어진다 ($1 \le m \le n \le 30$). 이어지는 $n$개 줄의 $i$번째 줄에는 문자열 $t_i$가 주어진다. 각 글자 $t_{i,j}$는 이 글자를 집합 $i$에 추가하는 연산을 뜻한다. 각 문자열은 비어 있지 않으며, 같은 글자는 한 번만 나타난다. 마지막 줄에는 패턴 $p_1 p_2 \ldots p_m$을 나타내는 소문자 문자열이 주어진다.

각 테스트 케이스마다 패턴이 집합들과 절대 매칭되지 않으면 "-1"을 출력한다. 그렇지 않으면 기댓값을 $\frac{p}{q}$라 할 때, $p \cdot q^{-1} \bmod 998\,244\,353$을 출력한다.

첫 번째 테스트 케이스에서 기댓값은 $\frac{1}{2} \cdot 1 + \frac{1}{2^2} \cdot 2 + \ldots = 2$이다.