题目描述

小豆参加了生物实验室，他主要研究蛋白质。
他现在研究的蛋白质是由 ( k ) 个氨基酸按一定顺序构成的。每一个氨基酸都可能有 ( a_i ) 种碱基序列 ( s_{i,j} ) 构成。
现在小豆有一个碱基串 ( s )，他想知道在这个碱基串上有多少种不同的组合方式可能得到这个蛋白质。
即求由 ( k ) 段字符串有序合并成的字符串 ( s_1s_2\cdots s_k )，有多少种不同方式能够匹配字符串 ( s ) 的某个连续子串。其中，( k ) 段字符串的选法不同，或者与 ( s ) 匹配的位置不同，都认为是不同的方式。

输入格式

第一行一个数，表示这个蛋白质由 ( k ) 个氨基酸构成。
第二行一个字符串 ( s )，表示小豆现在有的碱基串。
第三行开始接下来 ( k ) 行，表示第 ( i ) 个氨基酸可能的碱基序列：对于第 ( i ) 个氨基酸，( a_i ) 表示可能的碱基序列种数，接下来 ( a_i ) 个字符串表示这 ( a_i ) 种可能的碱基序列，用空格隔开。

输出格式

输出一个数，表示不同的方案数对 ( 10^9 + 7 ) 取模后的结果（不同的方案数指不同的子碱基串，或相同的碱基串但不同的氨基酸排列方式）。

样例

样例 1
输入：

2  
ABC  
2 A AB  
2 C BC  

输出：

2  

说明：

• 第一个氨基酸选 ( A )、第二个选 ( C )，合并为 ( AC )，无法匹配 ( ABC )，0 种；
• 第一个选 ( A )、第二个选 ( BC )，合并为 ( ABC )，匹配 ( ABC ) 的整个串，1 种；
• 第一个选 ( AB )、第二个选 ( C )，合并为 ( ABC )，匹配 ( ABC ) 的整个串，1 种；
• 第一个选 ( AB )、第二个选 ( BC )，合并为 ( ABBC )，无法匹配 ( ABC )，0 种；
  总共有 2 种方案。

样例 2
输入：

2  
AAA  
2 A AA  
2 A AA  

输出：

4  

说明：

• 第一个选 ( A )、第二个选 ( A )，合并为 ( AA )，可匹配 ( AAA ) 的第 1-2 位和第 2-3 位，2 种；
• 第一个选 ( A )、第二个选 ( AA )，合并为 ( AAA )，匹配 ( AAA ) 的第 1-3 位，1 种；
• 第一个选 ( AA )、第二个选 ( A )，合并为 ( AAA )，匹配 ( AAA ) 的第 1-3 位，1 种；
• 第一个选 ( AA )、第二个选 ( AA )，合并为 ( AAAA )，无法匹配 ( AAA )，0 种；
  总共有 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 )。