B - エターナルスタティックファイナル

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

トモアキ君は天下一王国流魔術の新しい呪文を習得しようと試みています。

トモアキ君は、自分が覚えているフレーズを組み合わせて呪文を詠唱します。

呪文の詠唱には同じフレーズを複数回使うことができます。

例えば aaa, bbb, ccc という 3 つのフレーズを記憶していた場合、aaaccc, aaabbb, cccaaaaaa といった呪文を詠唱することが可能です。

トモアキ君は、新しく習得しようとしている呪文を、覚えているフレーズを組み合わせて詠唱することができるか不安になりました。

トモアキ君のために、呪文を構築するためのフレーズの並べ方がどれくらいあるか数えるプログラムを作成してください。

並べ方の数は大きくなる可能性があるので、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 で割った余りを出力して下さい。


Source Name

天下一プログラマーコンテスト2014 予選B