裁缝

时间限制: 2000/1000 MS (Java/Others)

内存限制: 524288/524288 K (Java/Others)

问题描述

小团最近获得了美美团团国的裁缝资格证，成为了一个裁缝！现在小团有一个长度为n的大布料S（在这个国家布料其实是一个仅包含小写英文字母的字符串），小团可以将布料在任意位置剪切，例如布料abcd可以被裁剪为a与bcd 或ab与cd或abc与d ，不过，裁剪完之后是不能拼接起来的，因为小团还不是很擅长拼接布料。现在小团想知道能不能有一种裁剪方式能让他把布料恰好裁剪成客人要求的小布料。

形式化地，有一个串S，问是否能将其划分成m个不相交的连续子串，使得这些连续子串可以与要求的连续子串一一对应。两个串相对应是指这两个串完全相等。例如"aab"="aab" 但 "aab" ≠ "baa"

输入描述

第一行两个正整数n和m，分别表示大布料S长度和客人要求的小布料数量。

接下来一行一个长度为n的仅包含小写英文字母的串S，表示大布料的组成。

接下来一行m个数 x_1,x_2,…,x_m ，依次表示所要求的小布料长度。

接下来开始m行，每行一个长度为x_i的仅包含小写英文字母的串s_i，表示第i个小布料的组成。

对于40%的数据，n≤7,m≤4

对于另外30%的数据，n≤20,m≤7

对于所有数据，1≤m≤9,1≤n≤20 ,1≤x_i≤n且Σ_(i=1)^m x_i=n

输出描述

如果存在这样的方案，输出方案总数。如果不存在任何方案，输出0。两个方案A、B不相同当且仅当方案A中存在一个相对于原始长布料的裁剪位置i，而方案B中并未在该位置i裁剪。

例如aaaaaa 裁剪方案aaa|aaa 与方案 aaa|aaa是相同的方案。而方案aa|aaaa与方案aaaa|aa是不同的方案，虽然划分出的结果都是aa与aaaa，但前者在第二个a处进行了裁剪，后者并没有在这里进行裁剪，所以视为不同的裁剪方案。

输入样例

6 2

aaaaaa

4 2

aaaa

aa

输出样例

2

样例解释

有两种方案，第一种是aaaa|aa，第二种是aa|aaaa，'|'代表一次裁剪。