2251：青蛙的语言

在青蛙的世界里，构成语言的基本字符是$$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

厦门大学嘉庚学院第七届编程大赛

23-24(2)第6次线上赛