题目描述

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$.

ab
2
a
b

748683265

ab
4
aaa
abab
baba
bbb

1

提示

$\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$.