[TJOI2018]str

内存限制：256 MiB 时间限制：10 Sec

提交提交记录讨论

小豆参加了生物实验室。在实验室里，他主要研究蛋臼质。他现在研究的蛋臼质是由k个氨基酸按一定顺序构成的

。每一个氨基酸都可能有a种碱基序列si_j 构成。现在小豆有一个碱基串s，小豆想知道在这个碱基上都多少中

不同的组合方式可能得到这个蛋白质。即求由k段字符串有序合并成的字符串s1,有多少种不同方式能够匹配字符串

s，其中k段字符串的选法不同，或者与s匹配上的位置不同认为是不同的方式。

第一行一个数，表示这个蛋臼质由k个氨基酸。

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

第三行开始接下来k行表示第i个氨基酸可能的碱基序列，对于第i个氨基酸，ai表示这个氨基酸可能的碱基序列种数，

接下来ai个字符串表示这ai 种可能的碱基序列，用空格隔开。

1 ≤ k ≤ 100, |s| ≤ 10000,ai ≤ 10

输出一个数目标是不同的方案数

(不同的方案数是指不同的子碱基串或者相同的碱基串不同的氨基酸排列方式)

样例输入


			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种

#5337. [TJOI2018]str

题目描述

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示