問題文
文字列 S が与えられる。S は J,O,I,?の 4 つの文字で構成される。
？は、そこに J,O,I のどれが入 るか分からないということである。
JOI 文字列とは、次のようなものである。
・J が A 個、O が B 個、I が C 個 連続して並ぶ文字列 のことである。
・A>B>C かつ C>0 を満たさなければ ならない。
・よって、JOI 文字列は 6 文字以上でなければならない。
・例えば、"JJJOOI"や"JJJJJJJOOOOOOII"などはJOI文字列である。
JOI 文字列を【部分文字列として】文字列 S に含むものの通り数を 1,000,000,007 で割った余りを求めよ。
ただし、|S|≦5 のとき、必ず答えは 0 となる。
入力は、JOI という 3 文字の行で終わりとなる。
制約
1≦|S|≦200 を満たす。部分点
20 点分のテストケースは、1≦|S|≦10 を満たす。50 点分のテストケースは、1≦|S|≦40 を満たす。
100 点分のテストケースは、1≦|S|≦200 を満たす。
入力例
???????I?OI?J???J?I?
O???IJI???
?II?????OI
??O??????J
??OJ??IJ?O
??????????
JOI
出力例
480
0
9
9
0
433