시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB86360.000%

문제

Rikka has $n$ sets $S_1, S_2, \ldots, S_n$ consisting of lowercase English letters. A pattern $p_1 p_2 \ldots p_m$ of length $m$ is said to match the sets if there exists an index $i$ such that all the following conditions hold: $p_1 \in S_i$, $p_2 \in S_{i + 1}$, $\ldots$, $p_m \in S_{i + m - 1}$.

Initially, all sets are empty. Rikka has prepared some operations to make with the sets. Each operation has the form "add character $c$ into set $i$". Each round, Rikka will choose a random operation with equal probability and apply it. A single operation may be chosen and applied more than once.

Find the expected number of rounds until the pattern $p_1 p_2 \ldots p_m$ matches the sets.

입력

The first line contains an integer $T$ which denotes the number of test cases ($1 \le T \le 5$).

For each test case, the first line contains two integers $n$ and $m$ ($1 \leq m \leq n \leq 30$).

The $i$-th of the following $n$ lines contains a string $t_i$ consisting of lowercase English letters. Each letter $t_{i, j}$ denotes an operation which adds this letter into set $i$. Each of these strings is non-empty and contains every possible letter at most once.

The last line of each test case contains the pattern: a string $p_1 p_2 \ldots p_m$ consisting of lowercase English letters.

출력

For each test case, if the pattern will never match the sets, output "$-1$". Otherwise, output the integer $(p \cdot q^{-1}) \bmod 998\,244\,353$, where $\frac{p}{q}$ is the expected number of rounds.

예제 입력 1

1
1 1
ab
a

예제 출력 1

2

예제 입력 2

1
3 2
acb
cb
ab
cb

예제 출력 2

915057330

힌트

For the first sample test case, the expectation is $\frac{1}{2} \cdot 1 + \frac{1}{2^2} \cdot 2 + \ldots = 2$.