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

[problemUrl]: https://atcoder.jp/contests/tenka1-2014-qualb/tasks/tenka1_2014_qualB_b トモアキ君は天下一王国流魔術の新しい呪文を習得しようと試みています。 トモアキ君は、自分が覚えているフレーズを組み合わせて呪文を詠唱します。 呪文の詠唱には同じフレーズを複数回使うことができます。 例えば $ 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 $ 行で出力せよ。出力の末尾には改行をいれること。

### Sample Explanation 1 並べ方は $ 1 $ 通りしかありません。 ### Sample Explanation 2 並べ方は下記の $ 2 $ 通りがあります。 ``` eternal + static + final eternal + static + fin + al ``` ### Sample Explanation 3 並べ方は下記の $ 3 $ 通りがあります。 ``` abcdef abc + def abc + d + ef ``` ### Sample Explanation 4 並べ方は下記の $ 8 $ 通りがあります。 ``` aaaa aaa + a aa + aa aa + a + a a + aaa a + aa + a a + a + aa a + a + a + a ``` トモアキ君が覚えている`b`はこの呪文では使用しませんでした。 ### Sample Explanation 5 並べ方の数は大きくなる可能性があるので、$ 1000000007 $ で割った余りを出力して下さい。