AT_dwango2015_prelims_2 ニコニコ文字列

[problemUrl]: https://atcoder.jp/contests/dwango2015-prelims/tasks/dwango2015_prelims_2 $ 0 $ から $ 9 $ の数字から成る文字列 $ S $ が与えられます。 ある文字列 $ X $ について、$ X="25" $ または $ X="2525" $ または $ X="252525" $ …… というふうに $ "25" $ を何回か繰り返した文字列になっているとき、$ X $ はニコニコ文字列であるといいます。 たとえば $ "25" $ や $ "25252525" $ はニコニコ文字列ですが、$ "123" $ や $ "225" $ はニコニコ文字列ではありません。 あなたの仕事は、文字列 $ S $ について、ニコニコ文字列となるような連続した部分文字列の取り出し方が何通りあるかを答えることです。 文字列として同じであっても、取り出し位置が異なっていれば別々に数えます。

入力は以下の形式で標準入力から与えられる。 > $ S $ - $ 1 $ 行目には、文字列 $ S $ が与えられる。$ S $の長さは $ 1 $ 以上 $ 100,000 $ 以下である。また、$ S $ の各文字は $ 0 $ から $ 9 $ の数字のみから成る。

$ 1 $ 行目には、文字列 $ S $ からニコニコ文字列となるような連続した部分文字列を取り出す方法が何通りあるかを出力せよ。 **行末の改行を忘れると不正解と判定されるので注意すること。**

### 部分点 この問題には部分点が設定されています。 $ N≦2000 $ を満たすデータセット $ 1 $ にすべて正解すると、$ 30 $ 点が得られます。 追加制約のないデータセット 2 にすべて正解すると、上記のデータセットに加えてさらに $ 70 $ 点が得られ、全体で $ 100 $ 点が得られます。 ### Sample Explanation 1 $ S="2525" $のケースです。部分文字列が $ "25" $ となる取り出し方が $ 2 $ 通り、$ "2525" $ となる取り出し方が $ 1 $ 通りあるので合計 $ 3 $ 通りを出力します。