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