Counting Substhreengs

Interview

Time limit3sMemory limit256 MB

Summary

Count the contiguous digit-only substrings of S whose value is a multiple of 3.

Level: Medium4 of 10
Topics: Prefix sum, Math
Solved: No attempts yet

Problem

A substring is a string formed by choosing contiguous characters from a string. A substhreeng is a substring that meets two more requirements:

It is non-empty and consists entirely of base 10 digits.
Read in base 10, with any extra leading zeros allowed, its value is a multiple of 3.

For example, the string 130a303 contains 9 substhreengs: 3 three times, 30 and 0 twice each, and 303 and 03 once each. The substring 30a3 is not a substhreeng because it contains a character that is not a digit, and the substring 13 is not a substhreeng because 13 is not a multiple of 3.

Two substhreengs count as different when they have different lengths or start at different positions, even if the chosen characters are the same.

Given a string $S$ , count the substhreengs it contains.

Input

The first line contains a string $S$ . $S$ is non-empty and has at most $10^6$ characters. Each character of $S$ is a digit or a lowercase English letter.

Output

Print the number of substhreengs contained in $S$ on one line.

Examples3

Example 1
Input
```
130a303
```
Expected output
```
9
```
Example 2
Input
```
0000000000
```
Expected output
```
55
```
Example 3
Input
```
icpc2014regional
```
Expected output
```
2
```