#P7984. Pty loves book
Pty loves book
Pty 爱读书
题目描述
给定字符串 和包含 个带权单词 的词典,定义
$$f(s,l,r)=\sum_{i=1}^{m}\operatorname{occur}(s,l,r,t_i)w_i,$$其中 表示 在连续子串 内完整出现的次数。重叠出现分别计数;词典中相同单词的不同条目分别贡献各自的权值。
求
$$\sum_{l=1}^{|s|}\sum_{r=l}^{|s|}f(s,l,r)^5\pmod{10^9+7}.$$输入格式
第一行一个整数 ,表示测试组数。
每组先给出非空字符串 ,再给出整数 。接下来 行,每行一个非空单词 和权值 。字符串和单词按输入中的完整非空白串读取,不要求字符必须是小写字母。
输出格式
每组输出一行一个整数,表示答案。词典为空时答案为0。
样例
1
whkfqbw
3
h 3
hkfq 2
qb 2
75128
数据范围
。对每组数据,,,,。