A5755. 「TJOI2018」碱基序列
编程题
省选/NOI-
知识点
题目描述
小豆参加了生物实验室。在实验室里，他主要研究蛋白质。
他现在研究的蛋白质是由 $k$ 个氨基酸按一定顺序构成的。每一个氨基酸都可能有 $a$ 种碱基序列 $s_{i,j}$ 构成。
现在小豆有一个碱基串 $s$ ，小豆想知道在这个碱基上有多少种不同的组合方式可能得到这个蛋白质。
即求由 $k$ 段字符串有序合并成的字符串 $s_1$ ，有多少种不同方式能够匹配字符串 $s$ ，其中 $k$ 段字符串的选法不同，或者与 $s$ 匹配上的位置不同认为是不同的方式。
他现在研究的蛋白质是由 $k$ 个氨基酸按一定顺序构成的。每一个氨基酸都可能有 $a$ 种碱基序列 $s_{i,j}$ 构成。
现在小豆有一个碱基串 $s$ ，小豆想知道在这个碱基上有多少种不同的组合方式可能得到这个蛋白质。
即求由 $k$ 段字符串有序合并成的字符串 $s_1$ ，有多少种不同方式能够匹配字符串 $s$ ，其中 $k$ 段字符串的选法不同，或者与 $s$ 匹配上的位置不同认为是不同的方式。
输入格式
第一行一个数，表示这个蛋白质由 $k$ 个氨基酸。
第二行一个字符串 $s$ ，表示小豆现在有的碱基串。
第三行开始接下来 $k$ 行表示第 $i$ 个氨基酸可能的碱基序列，对于第 $i$ 个氨基酸， $a_i$ 表示这个氨基酸可能的碱基序列种数，接下来 $a_i$ 个字符串表示这 $a_i$ 种可能的碱基序列，用空格隔开。
第二行一个字符串 $s$ ，表示小豆现在有的碱基串。
第三行开始接下来 $k$ 行表示第 $i$ 个氨基酸可能的碱基序列，对于第 $i$ 个氨基酸， $a_i$ 表示这个氨基酸可能的碱基序列种数，接下来 $a_i$ 个字符串表示这 $a_i$ 种可能的碱基序列，用空格隔开。
输出格式
输出一个数，表示不同的方案数对 $10^9+7$ 取模后的结果（不同的方案数是指不同的子碱基串或者相同的碱基串不同的氨基酸排列方式）。
输入输出样例
输入 #1
2 ABC 2 A AB 2 C BC
输出 #1
2
输入 #2
2 AAA 2 A AA 2 A AA
输出 #2
4
说明/提示
对于 $30\%$ 的数据， $1 \leq k \leq 25$, $|s| \leq 10000,a_i \leq 3$ 。
对于 $100\%$ 的数据， $1 \leq k \leq 100$, $|s| \leq 10000,a_i \leq 10$ 。
对于 $100\%$ 的数据， $1 \leq k \leq 100$, $|s| \leq 10000,a_i \leq 10$ 。