ニコニコ文字列

## 题目描述 给出由$0-9$数字构成的字符串$S$。 对某个字符串$X$来说，如果$X=$"25"或$X=$"2525"或$X=$"252525"......$X$像这样由"25"重复多次组成，那么就称$X$为niconico字符串。例如"25"或"252525"就是niconico字符串，而"123"或"225"不是niconico字符串。 你的任务是，对于字符串$S$，请回答出$S$中有多少个子串为niconico字符串。即使子串相同，但是如果子串在原串中位置不同，也要分别计入总数中。 ## 输入 输入按以下形式： ``` S ``` - 第一行给出字符串$S$。$S$的长度在1或以上，$100,000$或以下。另外，$S$中的每个字符为从$0$到$9$的数字。 ## 部分分 对于30%的数据，满足$N≤2000$ ## 输出 在第一列中，输出字符串$S$中含有多少个子串为niconico字符串。 ** 请注意，如果忘记行末换行会判为WA！** ## 样例 样例见下方日文原题面。 输出样例#5为： ``` 0 ``` 感谢@ミク 提供的翻译

[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 $ からニコニコ文字列となるような連続した部分文字列を取り出す方法が何通りあるかを出力せよ。 **行末の改行を忘れると不正解と判定されるので注意すること。**

2525

3

1251251252525

8

25225

2

252252252252252252

6

20061212

0

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