Logo Universal Online Judge

UOJ

时间限制:2 s 空间限制:1024 MB
统计

Notice

标程 TLE 了,因此时限变成 $2s$。

Description

给定长为 $n$ 的串 $s$ 和 $m$ 个串 $t_i$。

定义 $h(s, l, r) = \sum\limits_{i = 1}^m occur(s[l, r], t)\times w_i$,其中 $occur(s, t)$ 表示 $t$ 在 $s$ 中的出现次数。

求 $\sum\limits_{i = 1}^n\sum\limits_{j = i}^n h(s, i, j)^5\bmod 998244353$。

Input

第一行一个数 $T$,表示数据组数。

对于每组数据,第一行一个串 $s$。

第二行一个整数 $m$。

然后 $m$ 行,每行一个串 $t_i$ 和一个整数 $w_i$。

Output

$T$ 行每行一个非负整数,表示答案。

Sample Input #1

1
gongxinifaxianqiandaoti
3
ia 1
g 2
axia 3

Sample Output #1

1157160

Sample #2

Sample

Range

  • $\text{subtask}1(10\ \text{pts})$:$n, m, |t_i|\le 50$。

  • $\text{subtask}2(30\ \text{pts})$:$s, t_i$ 的每个字符在 ${a, b}$ 中随机生成,$w_i$ 在 $[0, 998244353)$ 中随机生成。

  • $\text{subtask}3(30\ \text{pts})$:$T = 1$。

  • $\text{subtask}4(30\ \text{pts})$:无特殊限制。

对于 $100\% $ 的数据,保证 $1\le T\le 5$,对于每组数据 $1\le n, \sum |t_i|, m\le 5\times 10^5, 0\le w_i < 998244353$,所以字符都是小写字母。