题目描述

小豆参加了生物实验室。在实验室里，他主要研究蛋白质。他现在研究的蛋白质是由 $k$ 个氨基酸按一定顺序构成的。每一个氨基酸都可能有 $a$ 种碱基序列 $s_{i,j}$ 构成。

现在小豆有一个碱基串 $s$，小豆想知道在这个碱基上都多少种不同的组合方式可能得到这个蛋白质。即求由 $k$ 段字符串有序合并成的字符串 $s_1$，有多少种不同方式能够匹配字符串 $s$，其中 $k$ 段字符串的选法不同，或者与 $s$ 匹配上的位置不同认为是不同的方式。

输入格式

第一行一个数，表示这个蛋白质由 $k$ 个氨基酸组成。

第二行一个字符串 $s$，表示小豆现在有的碱基串。

第三行开始接下来 $k$ 行表示第 $i$ 个氨基酸可能的碱基序列，对于第 $i$ 个氨基酸，$a_i$ 表示这个氨基酸可能的碱基序列种数，接下来 $a_i$ 个字符串表示这 $a_i$ 种可能的碱基序列，用空格隔开。

输出格式

输出一个数目标是不同的方案数（不同的方案数是指不同的子碱基串或者相同的碱基串不同的氨基酸排列方式）。

答案对 $10^9+7$ 取模。

2
ABC
2 A AB
2 C BC

2

2
AAA
2 A AA
2 A AA

4

提示

样例 1 解释

• 第一个选 $\tt A$ 第二个选 $\tt C$，得到 $\tt AC$ 能够与 $\tt ABC$ 产生 $0$ 种匹配方式；
• 第一个选 $\tt A$ 第二个选 $\tt BC$，得到 $\tt ABC$ 能够与 $\tt ABC$ 产生 $1$ 种匹配方式；
• 第一个选 $\tt AB$ 第二个选 $\tt C$，得到 $\tt ABC$ 能够与 $\tt ABC$ 产生 $1$ 种匹配方式；
• 第一个选 $\tt AB$ 第二个选 $\tt BC$，得到 $\tt ABBC$ 能够与 $\tt ABC$ 产生 $0$ 种匹配方式。

所以一共 $2$ 种。

样例 2 解释

• 第一个选 $\tt A$ 第二个选 $\tt A$，得到 $\tt AA$ 能够与 $\tt AAA$ 产生 $2$ 种匹配方式；
• 第一个选 $\tt A$ 第二个选 $\tt AA$，得到 $\tt AAA$ 能够与 $\tt AAA$ 产生 $1$ 种匹配方式；
• 第一个选 $\tt AA$ 第二个选 $\tt A$，得到 $\tt AAA$ 能够与 $\tt AAA$ 产生 $1$ 种匹配方式；
• 第一个选 $\tt AA$ 第二个选 $\tt AA$,得到 $\tt AAAA$ 能够与 $\tt AAA$ 产生 $0$ 种匹配方式。

所以一共 $4$ 种。

数据范围及约定

• 对于 $30\%$ 的数据，$1\leq k\leq 25$，$1\le |s|\leq 10000$，$1\le a_i\leq 3$。
• 对于 $100\%$ 的数据，$1\leq k\leq100$，$1\le |s|\leq 10000$，$1\le a_i \leq10$。碱基序列的长度均不超过 $15$。字符集为大写字母。