Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Divisible by 3

By bisnu_sarkar · Limits 1s, 512 MB

You will be given a string containing digits. You have to say the number of sub strings whose sum is divisible by 3.

Input

The only line of input containing a string s. (1 ≤ |s| ≤ 106), |s| denotes length of the string. The characters will be between 0 to 9.

Output

The output will contain the total number of substring sum of which are divisible by 3.

Sample

InputOutput
312012
11

Discussion

Statistics


80% Solution Ratio

skmonirEarliest, 1M ago

RipAndTearFastest, 0.0s

skmonirLightest, 1.0 MB

Jarif_RahmanShortest, 261B

Submit

Login to submit