Problem Description

You are given a string $ S $ consisting of digits from $ 0 $ to $ 9 $.

For a string $ X $, if $ X = "25" $ or $ X = "2525" $ or $ X = "252525" $ and so on, which means $ X $ is a string formed by repeating $ "25" $ multiple times, then $ X $ is called a Niconico String. For example, $ "25" $ and $ "25252525" $ are Niconico Strings, but $ "123" $ and $ "225" $ are not.

Your task is to determine how many ways you can extract contiguous substrings from $ S $ that are Niconico Strings. Even if the substrings are the same, they should be counted separately if they are extracted from different positions.

Input Format

The input is given from the standard input in the following format:

$ S $

• The first line contains the string $ S $. The length of $ S $ is between $ 1 $ and $ 100,000 $ inclusive. Each character of $ S $ is a digit from $ 0 $ to $ 9 $.

Output Format

Output a single line containing the number of ways to extract contiguous substrings from $ S $ that are Niconico Strings.

Note that omitting the newline at the end of the line will result in an incorrect answer.

Sample Input and Output

Sample Input #1

2525

Sample Output #1

3

Sample Input #2

1251251252525

Sample Output #2

8

Sample Input #3

25225

Sample Output #3

2

Sample Input #4

252252252252252252

Sample Output #4

6

Sample Input #5

20061212

Sample Output #5

0

Notes/Hints

Partial Points

This problem has partial points.

If you solve all cases of dataset 1 where $ N ≤ 2000 $, you will get $ 30 $ points. If you solve all cases of dataset 2 without additional constraints, you will get an additional $ 70 $ points on top of the previous dataset, totaling $ 100 $ points.

Sample Explanation 1

For the case $ S = "2525" $. There are $ 2 $ ways to extract the substring $ "25" $ and $ 1 $ way to extract the substring $ "2525" $, so the total is $ 3 $ ways.

见题面 Input 部分

见题面 Output 部分