Problem H: 字符串游戏

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

Description


小 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

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 互不相同，保证 ，

Output

输出共 m 行，输出一个整数，表示答案对 10^9 + 7 取模后的结果。

Sample Input复制

3 3
a
ab
abc
aababc
aabababc
ccaaabbb

Sample Output复制

48
106
73