P15659 [ICPC 2025 Jakarta R] 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. - Initially, you have an empty string $U$. - For $n$ times, choose a string uniformly at random among $S_1, S_2, \dots, S_K$, and append that string to $U$. - 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 998\;244\;353$.

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 $1\;000\;000$.

Output the limit $pq^{-1} \bmod 998\;244\;353$.

$\textit{Explanation of Sample 1:}$ It can be shown that $\lim\limits_{n \to \infty} f(n) = \frac{1}{4}$. $\textit{Explanation of Sample 2:}$ It can be shown that $\lim\limits_{n \to \infty} f(n) = 1$.