给定 $K$ 个由小写拉丁字母组成的字符串 $S_1, S_2, \dots, S_K$。同时给定一个字符串 $T$。 定义函数 $f(n)$（其中 $n$ 为整数）如下：

1. 初始时，你有一个空字符串 $U$。
2. 重复 $n$ 次操作：从 $S_1, S_2, \dots, S_K$ 中等概率随机选择一个字符串，并将其追加到 $U$ 的末尾。
3. 令 $E_n$ 为 $T$ 在 $U$ 中作为子串出现的次数的期望值。则 $f(n) = E_n/n$。

可以证明 $\lim_{n \to \infty} f(n)$ 存在，且可以写成有理数 $p/q$ 的形式。请计算 $pq^{-1} \pmod{998\,244\,353}$。

输入格式

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

输出格式

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

样例

输入 1

ab
2
a
b

输出 1

748683265

说明 1

可以证明 $\lim_{n \to \infty} f(n) = \frac{1}{4}$。

输入 2

ab
4
aaa
abab
baba
bbb

输出 2

1

说明 2

可以证明 $\lim_{n \to \infty} f(n) = 1$。