问题文

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

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

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

输入

从标准输入读取输入数据，格式如下：

$S$

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

部分点

此问题设置了部分点。

如果通过所有满足$N≦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