007 - イワシロ・イッツァ
時間制限 1 秒 / メモリ制限 256 MB / 得点 10 / x 1 /
問題
古代国家イワシロを発見し調査を進めた我々研究者は、ついにイワシロの中心部にある神殿を発見した。神殿にはイワシロの神にささげた石版が保管されていた。石版には、文章と呪文が一つずつ、2つの文字列が書かれていた。
イワシロでは呪文が文章の中に、何回現れるかが重要な意味を持つ。ただし、呪文に含まれるすべての文字が順番に、文章の中にとびとびで現れるものも1回現れていると考える。例えば、文章が"abab" で、呪文が "ab" であれば、連続でないものも含めて "ab" は "abab" の中に3回現われている( abab, abab, abab の3通り)。
文章と呪文が与えられたとき、呪文が文章の中に何回現れるかを出力するプログラムを作成せよ。
入力
入力は以下の形式で与えられる。
t b
1行目に、石版に書かれた文章を表す文字列tが与えられる。2行目に、石版に書かれた呪文を表す文字列bが与えられる。どちらの文字列も英小文字だけから成る、長さが1以上1000以下の文字列である。
出力
呪文が文章の中に何回現れるかを1行に出力する。ただし、出力すべき値は非常に大きくなりうるので、代わりに 1,000,000,007 で割った余りを出力する。
入出力例
入力例 1
abab ab
出力例 1
3
入力例 2
aaaabaaaabaaaabaaaab aaaaa
出力例 2
4368
入力例 3
data structure
出力例 3
0