Time Limit: 2 sec / Memory Limit: 256 MB
問題文
うなぎは太鼓ゲームに興じています。太鼓ゲームは、画面に表示される文字列に合わせて太鼓を叩くゲームです。表示されている文字列が S である場合は太鼓の中心を叩き、T である場合は太鼓のふちを叩きます。このゲームではいくつかの文字列が 1 列に表示され、それらの文字列に合わせて順番通りに太鼓を叩くとゲームをクリアできます。しかし、画面に表示されている文字列同士の間隔が狭すぎて、どこで文字列が区切られているのかが分かりません。
ゲームをクリアしたいうなぎは、画面に表示された文字列の正しい区切り方の個数を数えることにしました。ただし正しい区切り方とは、文字列を区切る方法であって、区切られた各部分の文字列が文字列 S または文字列 T と一致しているもののことを指します。
入力
入力は以下の形式で標準入力から与えられる。
X S T
- 1 行目には、画面に表示されている文字列 X (1 ≦ |X| ≦ 1000) が与えられる。ただし、|X| は文字列 X の長さを表すものとします。
- 2 行目には、太鼓の中心を叩くことを指示する文字列 S (1 ≦ |S| ≦ |X|) が与えられる。
- 3 行目には、太鼓のふちを叩くことを指示する文字列 T (1 ≦ |T| ≦ |X|, S \neq T) が与えられる。
- 入力される文字列は全てアルファベット小文字(
a
-z
)のみから構成される。 - 画面に表示された文字列の正しい区切り方は 1 通り以上存在することが保証されている。
出力
画面に表示された文字列の正しい区切り方の個数を 1,000,000,007 (10^9+7) で割った余りを 1 行に出力せよ。また、出力の末尾には改行を入れること。
入力例1
dondonkatsudon don katsu
出力例1
1
don,don,katsu,don のように区切ることが出来ます。
また、それ以外の正しい区切り方は存在しません。
入力例2
aaaaa aaa aa
出力例2
2
aaa,aa のように区切る方法と、aa,aaa のように区切る方法の 2 通りが存在します。
入力例3
ffffffffffffffffffffffffffffffffffffffffffffffffffffffff f ff
出力例2
435293607
答えは非常に大きくなる可能性があるため、1,000,000,007 で割った余りを求めることを忘れないようにして下さい。