Problem H: 字符串游戏

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $0$ 正确数量 $0$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签

小 A 拥有 n 个由小写字母构成的字符串 {Sn},小 B 拥有 m 个由小写字母构成的字符串 {Tn}。

现在他们要玩一个游戏,小 B 会每次给定一个字符串 P。对于字符串 P ,假设 P = A + B + C(A,B,C 均为字符串,A,B,C可以为空串,+ 表示字符串拼接),小 A 可以通过一次神奇的操作将字符串 P 变为 B。若此时存在一个小 A 拥有的字符串 Si,满足 Si = P。则记为小 A 胜利。

我们可以把一次操作 P = A + B + C 描述成一个四元组 (P, A, B, C) ,认为两个操作 (P0, A0, B0, C0) ,(P1, A1, B1, C1) 相同,当且仅当 P0 = P1, A0 = A1, B0 = B1, C0 = C1

每次游戏前,小 B 会告诉小 A 他这次给定的字符串是 Ti 的一个子串(只要子串位置不相同则视作不同)。小 A 想知道,对于小 B 选取子串的所有方法,他能通过 一次 神奇的操作获胜的操作种类数之和。由于答案较大,请对 109 + 7 取模之后输出。

Input

第一行给定两个正整数 n, m(1 ≤ n ≤ 2 × 10^5, 1 ≤ m ≤ 10^6),表示小 A 拥有的字符串数量和小 B 拥有的字符串数量。

接下来 n 行,每行给出一个小写字母构成的字符串 Si(1 ≤ |Si| ≤ 2 × 10^5)。

接下来 m 行,每行给出一个小写字母构成的字符串 Ti(1 ≤ |Ti| ≤ 1 × 10^6)。

保证 Si 互不相同,保证 

输出共 m 行,输出一个整数,表示答案对 10^9 + 7 取模后的结果。
3 3
a
ab
abc
aababc
aabababc
ccaaabbb
48
106
73