#dwango2015prelims2. [dwango2015_prelims_2]ニコニコ文字列

[dwango2015_prelims_2]ニコニコ文字列

问题文

给定一个由数字0到9组成的字符串S。

如果一个字符串X是由"25"重复若干次得到的,即X="25"或X="2525"或X="252525"......,那么称为一个Niconico字符串。例如,"25"和"25252525"都是Niconico字符串,但"123"和"225"不是。

你的任务是计算字符串S中有多少种连续的子字符串可以被提取出来,使其成为一个Niconico字符串。即使作为字符串是相同的,如果提取的位置是不同的,则视为不同的子字符串。


输入

从标准输入读取输入数据,格式如下:

SS

  • 第1行包含一个字符串S。S的长度在1到100,000之间。S的每个字符都是由数字0到9组成的。

部分点

此问题设置了部分点。

如果通过所有满足N2000N≦2000的数据集1,将获得30分。如果通过所有满足附加约束条件的数据集2,将获得上述数据集的70分,总共获得100分。

输出

在第1行输出从字符串S中提取出的连续子字符串,使其成为一个Niconico字符串的方法数。

注意不要省略行末的换行符。


示例1


2525

输出示例1


3

考虑S="2525"的情况。共有2种方式可以提取子字符串"25",1种方式可以提取子字符串"2525",因此总共有3种方式。


示例2


1251251252525

输出示例2


8

示例3


25225

输出示例3


2

示例4


252252252252252252

输出示例4


6

示例5


20061212

输出示例5


0