| 问题描述 |
|---|
在青蛙的世界里，构成语言的基本字符是$$26$$个小写字母，每个单词由其中几个字母构成，而每句话又是由几个单词拼凑而成。 青蛙公主不喜欢在单词和单词之间留空格，所以一句话中一个空格都不会有，所有单词都直接连在了一起。 于是青蛙王子很困扰，因为有时候青蛙公主说的话可以有好几种不同的单词拆分方法，可以理解成不同的意思。 现在青蛙公主说了很长的一句话，请帮青蛙王子看看，这句话有多少种不同的理解方法？ |
| 输入描述 |
第一行是一个正整数$$n$$表示测试案例的数量。（$$n \le 3$$） 每组案例先是一个正整数$$m$$，表示语言中有$$m$$个单词。（$$m \le 50$$） 然后是$$m$$个互不相同的字符串，表示这$$m$$个单词。单词只由小写字母组成，每个单词的长度小于等于$$100$$。 最后是一个不带空格的小写字母组成的字符串（长度不超过$$10000$$），表示青蛙公主说的一句话。 |
| 输出描述 |
针对每组案例，输出一个整数，表示这句话有多少种不同的理解方法，这个值可能非常大，只要输出答案对$$100000007$$取模的结果即可。 如果语句有错，即无法用现有的单词理解，则输出$$0$$。 |
| 样例输入复制样例 |
2 2 ab cd acd 2 a aa aaa |
| 样例输出 |
0 3 |
| 提示说明 |
aaa 可以理解成： a、a、a a、aa aa、a |
| 相关 |