시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 8 | 6 | 3 | 60.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 ab a
2
1 3 2 acb cb ab cb
915057330
For the first sample test case, the expectation is $\frac{1}{2} \cdot 1 + \frac{1}{2^2} \cdot 2 + \ldots = 2$.