匹配

题目描述:

给定k个字符串以及长度为n的母串可选字母的集合，问母串要完整出现给定的k个字符串的方案数，答案模1000000007，字符仅包含小写字母。

输入格式:

第一行两个整数n、k，表示字符串的长度和给定字符串的个数。

接下来k行每行一个字符串。

接下来一行1个整数m表示可选字母集合内元素个数。

接下来一行给出一个长为m的字符串，表示字母的集合（可能有重复）。

输出格式:

一个整数ans，表示方案数。

样例输入:

3 2
cr
rh
4
acrh

样例输出:

1

提示:

【样例解释】

只有crh符合。

 

【数据范围】

30%的数据n<=10，m<=3。

60%的数据n<=40。

另有10%的数据k=0。

另有10%的数据m=1。

100%的数据n<=100，m<=10，k<=8，给定字符串长度<=30。

时间限制: 1000ms
空间限制: 256MB

---