問題文

うなぎは太鼓ゲームに興じています。太鼓ゲームは、画面に表示される文字列に合わせて太鼓を叩くゲームです。表示されている文字列が S である場合は太鼓の中心を叩き、T である場合は太鼓のふちを叩きます。このゲームではいくつかの文字列が 1 列に表示され、それらの文字列に合わせて順番通りに太鼓を叩くとゲームをクリアできます。しかし、画面に表示されている文字列同士の間隔が狭すぎて、どこで文字列が区切られているのかが分かりません。

ゲームをクリアしたいうなぎは、画面に表示された文字列の正しい区切り方の個数を数えることにしました。ただし正しい区切り方とは、文字列を区切る方法であって、区切られた各部分の文字列が文字列 S または文字列 T と一致しているもののことを指します。

入力例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 で割った余りを求めることを忘れないようにして下さい。