P15659 [ICPC 2025 Jakarta R] Mugen E

给定 $K$ 个由小写字母组成的字符串 $S_1, S_2, \dots, S_K$。同时给定一个字符串 $T$。 定义函数 $f(n)$，其中 $n$ 是一个整数，定义如下。 - 初始时，你有一个空字符串 $U$。 - 进行 $n$ 次操作，每次操作从 $S_1, S_2, \dots, S_K$ 中均匀随机地选择一个字符串，并将其追加到 $U$ 的末尾。 - 设 $E_n$ 为 $T$ 在 $U$ 中作为子串出现的次数的期望值。那么，$f(n) = E_n / n$。 可以证明，$\lim\limits_{n \to \infty} f(n)$ 存在，并且可以写成一个有理数 $p / q$。求 $pq^{-1} \bmod 998\;244\;353$ 的值。

第一行包含一个由小写字母组成的字符串 $T$（$1 \leq |T| \leq 5000$）。 第二行包含一个整数 $K$（$1 \leq K \leq 5000$）。 接下来的 $K$ 行，每行包含一个由小写字母组成的字符串 $S_i$（$1 \leq |S_i| \leq 5000$）。 所有 $|S_i|$ 的总和不超过 $1\;000\;000$。

输出极限值 $pq^{-1} \bmod 998\;244\;353$。

**样例 1 解释：** 可以证明 $\lim\limits_{n \to \infty} f(n) = \frac{1}{4}$。 **样例 2 解释：** 可以证明 $\lim\limits_{n \to \infty} f(n) = 1$。 翻译由 DeepSeek V3.2 完成