Migrated from Lutece 2460 第二章：北境之王的现身

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

上一集：上一集

第二章：北境之王的现身

「不要！！！」 从远处传来一声呐喊。

只见个高大魁梧俊朗男，头顶金刚不坏秘银盔，身披梅花簇雪紫金袍，腰束九色玲珑翡翠带，脚踏北寒霜雪凌冽风。让人一看就知道身份不凡。而糖正认得，此人便是沙河的统御者、北国的掌管者、数据结构的精通者、几何的大师、大腿自动机、 ZXyang 的队友，北境之王 HeRaNO 。

ZXyang 看到 HeRaNO 来了，抹去嘴角的血，昏死了过去。

糖知道， ZXyang 和 HeRaNO 曾经都是这个世界的元老，可惜，由于某些特殊原因，当初拯救世界（过去的故事）的他们莫名被贬， HeRaNO 还可以继续做北境之王，而 ZXyang 只能到这里当一个看门的。人的码力是要靠吸取天地灵气的。对于像 ZXyang 这样的普通人来说，在这种边远的地区守门，自然而然带来的便是码力的亏损。久而久之，当年黄榜上赫赫有名的人物，到了如今算法实力连蓝榜都不如了。

但是，面前的 HeRaNO 不一样。北境虽不及中原，但仍可称得上一块风水宝地。HeRaNO 的实力并没有收到大幅度的消减。现在 HeRaNO 想要挡路，只怕不是那么轻松就能解决的。但是即便如此，为了打破大陆的现状，糖也必须要去中原，为了解决那长久以来的沉寂，让算法界能有新人出现发明新的算法。

糖虽然只是一个穿着水手服的妙龄少女，论装备远不及 HeRaNO ，但是算法的实力并不是仅仅靠着装备便能改变的。糖心中早已了解，怎么样把字符串和数据结构结合，这样，哪怕 ZXyang 当场苏醒，和 HeRaNO 一起发动进攻，也不至于当场被打败。

「看你这样子，他还真没说错。」HeRaNO 突然开口了。「你可知道自动机理论？」

糖心中一惊： HeRaNO 已经猜到我将使用什么招数了吗？ 嘴上却只能说道：「知，知道呀，我这种算法美少女怎么可能不知道自动机理论呢。」

HeRaNO 微微一笑：「好吧，那么让我来考考你。如果你真的懂的话，那我就把我的功力传给你。」

说罢，HeRaNO 稍稍屏气凝神，右手微微抬起，而后轻轻一翻。这天下间顿时挂起一阵寒风。寒风中隐约可见一些字符。而糖也不甘示弱，悄悄调整呼吸。糖现在的实力虽不及 HeRaNO ，但驱动码力护体还是可以做到的。但是 HeRaNO 不愧是老将，尽管糖已经百般思索，仔细观察，仍然难以发现破绽。

而 HeRaNO 的动作开始大了起来，老练地翻动着双手，紧接着全身都开始随着狂风的韵律而舞动。甚至风中都开始出现了冰雪。而此时，糖看着 HeRaNO 的身法，突然领悟了。

HeRaNO 会先给出一个串 $s$ 。 然后给出 $m$ 个串 $t_1,t_2\dots t_m$ 对应 $m$ 个集合。 糖需要回答对于所有的 $1\leq i\leq m$ ，有 $T_i\in t_i$ 的字符串 $T$ ，$s$ 在这些 $T$ 中一共出现了多少次。 输入保证对于所有 $t_i$ ， 每个 $t_i$ 中每个字母最多出现一次。 本题中所有串的字符集为小写字母。 在交题之后请检查自己的空间是否超限，由于 lutece 目前没有判定 MLE 的功能，所以如果题解中交的代码空间超限，很有可能会被判零分。

Input

第一行一个串 $s$ 。 第二行一个数 $m$。 第三行 $m$ 个数，分别代表每个串的串长。 接下来 $m$ 行，每行包括一个字符串 $t_i$ 。

Output

输出一个数代表答案对 $10^9+7$ 取模后的结果。

Samples

abc
4
1 2 2 1
a
ab
bc
c

2

abc
4
3 3 3 3
abc
abc
abc
abc

6

ab
5
3 3 3 3 4
abc
abc
abc
abc
abcd

135

Constraints

$|s|\leq10^3,\sum |t_i| \leq 2\times10^6$

Note

对于样例一产生的合法 $T$ 串：

第一个位置可以是 a 第二个位置可以是 ab 第三个位置可以是 bc 第四个位置可以是 c

所以所有合法的 $T$ 串有： aabc abbc aacc abcc

其中 $s$ 串在 aabc 和 abcc 中各出现一次。

Resources

2020 UESTC ICPC Training for String and Search Algorithm