35170번 - Mugen E 다국어

You are given $K$ strings $S_1, S_2, \dots, S_K$ of lowercase Latin letters. You are also given a string $T$.

Define a function $f(n)$, where $n$ is an integer, as the following.

1. Initially, you have an empty string $U$.
2. For $n$ times, choose a string uniformly at random among $S_1, S_2, \dots, S_K$, and append that string to $U$.
3. Let $E_n$ be the expected value of the number of occurrences of $T$ in $U$ as a substring. Then, $f(n) = E_n / n$.

It can be proven that $\lim\limits_{n \to \infty} f(n)$ exists and can be written as a rational number $p / q$. Find $pq^{-1} \bmod 998244353$.

The first line contains the string $T$ ($1 \leq |T| \leq 5000$) consisting of lowercase Latin letters. The second line contains an integer $K$ ($1 \leq K \leq 5000)$. Each of the next $K$ lines contains $S_i$ ($1 \leq |S_i| \leq 5000$) consisting of lowercase Latin letters. The sum of $|S_i|$ does not exceed $1000000$.

Output the limit $pq^{-1} \bmod 998244353$.