B - エターナルスタティックファイナル
Editorial
/ 
/ 
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 で割った余りを出力して下さい。