問題文
智明君正在尝试学习天海一王国风格魔法的新咒语。
智明通过组合他所记住的短语来吟唱咒语。
你可以多次使用同一个短语来施展法术。
例如 第 aaa, bbb, ccc 这就是所谓的 3 如果你记住了一个短语, 可以吟唱诸如aaaccc, aaabbb, cccaaaaaa 之类的咒语。
智明担心他是否能够通过组合他所记住的短语来吟唱他试图学习的新咒语。
请给Tomoaki-kun编写一个程序来计算短语可以排列多少种方式来构造咒语。
由于排列方法的数量可能很大,1000000007 后的余数。
入力
输入是按以下格式从标准输入给出的。
N S T1 T2 : TN
- 1 第一行显示智明已记住的短语数。 N (1 \leq N \leq 100) 。 表示
- 2 智明想要学习的咒语在第一行。 S 。 表示
- S 的长度 |S| 是 您也可以写 1 \leq |S| \leq 1000 很满意。
- S 由小写字母组成。
- 3 从行 N 这行是智明已经记住的短语。 Ti 。 表示
- Ti 的长度 |Ti| 是 您也可以写 1 \leq |Ti| \leq 1000 很满意。
- Ti 由小写字母组成。
- i \neq j 如果 Ti \neq Tj 很满意。
出力
排列短语以构建咒语的方法数量 1000000007 后的余数 在 1 行。在输出末尾添加换行符。
入力例1
3 eternalstaticfinal eternal static final
出力例1
1
如何排列它们 1 只有一条街。
入力例2
5 eternalstaticfinal eternal static final fin al
出力例2
2
安排如下。 2 有一条街。 转至
eternal + static + final eternal + static + fin + al
入力例3
5 abcdef abc def abcdef d ef
出力例3
3
安排如下。 3 有一条街。 转至
abcdef abc + def abc + d + ef
入力例4
5 aaaa a aa aaa aaaa b
出力例4
8
安排如下。 8 有一条街。 转至
aaaa aaa + a aa + aa aa + a + a a + aaa a + aa + a a + a + aa a + a + a + a
智明君记得
此法术中未使用b。
有
入力例5
10 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa a aa aaa aaaa aaaaa aaaaaa aaaaaaa aaaaaaaa aaaaaaaaa aaaaaaaaaa
出力例5
146491918
由于排列方法的数量可能很大,1000000007 后的余数。