You will be given a string containing digits. You have to say the number of sub strings whose sum is divisible by 3.
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.
The output will contain the total number of substring sum of which are divisible by 3.
Input | Output |
---|---|
312012 | 11 |