#P7984. Pty loves book

Pty loves book

Pty 爱读书

题目描述

给定字符串 ss 和包含 mm 个带权单词 (ti,wi)(t_i,w_i) 的词典,定义

$$f(s,l,r)=\sum_{i=1}^{m}\operatorname{occur}(s,l,r,t_i)w_i,$$

其中 occur⁡(s,l,r,ti)\operatorname{occur}(s,l,r,t_i) 表示 tit_i 在连续子串 s[l…r]s[l\ldots r] 内完整出现的次数。重叠出现分别计数;词典中相同单词的不同条目分别贡献各自的权值。

求

$$\sum_{l=1}^{|s|}\sum_{r=l}^{|s|}f(s,l,r)^5\pmod{10^9+7}.$$

输入格式

第一行一个整数 TT,表示测试组数。

每组先给出非空字符串 ss,再给出整数 mm。接下来 mm 行,每行一个非空单词 tit_i 和权值 wiw_i。字符串和单词按输入中的完整非空白串读取,不要求字符必须是小写字母。

输出格式

每组输出一行一个整数,表示答案。词典为空时答案为0。

样例

1
whkfqbw
3
h 3
hkfq 2
qb 2
75128

数据范围

1≤T≤111\le T\le11。对每组数据,1≤∣s∣≤5×1051\le |s|\le5\times10^5,0≤m≤5×1050\le m\le5\times10^5,∑i∣ti∣≤5×105\sum_i|t_i|\le5\times10^5,1≤wi<109+71\le w_i<10^9+7。