← 返回题目列表

AtCoder · tenka1_2014_qualB_b

B. 永恒的静态决赛

中文机器翻译题面 查看原题

問題文

智明君正在尝试学习天海一王国风格魔法的新咒语。

智明通过组合他所记住的短语来吟唱咒语。

你可以多次使用同一个短语来施展法术。

例如 第 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 后的余数。