题目描述

给定 $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$。

ab
2
a
b

748683265

ab
4
aaa
abab
baba
bbb

1

提示

样例 1 解释： 可以证明 $\lim\limits_{n \to \infty} f(n) = \frac{1}{4}$。

样例 2 解释： 可以证明 $\lim\limits_{n \to \infty} f(n) = 1$。

翻译由 DeepSeek V3.2 完成