3의 배수 부분문자열 세기

문자열에서 연속한 문자를 골라 만든 문자열을 부분문자열이라고 한다. 여기서는 조건을 더 붙인 3의 배수 부분문자열을 센다. 3의 배수 부분문자열은 다음 두 조건을 모두 만족하는 부분문자열이다.

1. 비어 있지 않고, 모든 문자가 10진수 숫자이다.
2. 앞에 0이 더 붙어 있어도 그대로 10진수로 읽었을 때 그 값이 3의 배수이다.

예를 들어 문자열 130a303에는 3의 배수 부분문자열이 9개 있다. 3이 세 번, 30과 0이 각각 두 번, 303과 03이 각각 한 번 나온다. 부분문자열 30a3은 숫자가 아닌 문자를 포함하므로 조건을 만족하지 않고, 부분문자열 13은 13이 3의 배수가 아니므로 조건을 만족하지 않는다.

길이가 다르거나 시작 위치가 다르면, 고른 문자가 같아도 서로 다른 3의 배수 부분문자열로 센다.

문자열 $S$가 주어질 때, $S$가 포함하는 3의 배수 부분문자열의 개수를 구하라.

첫째 줄에 문자열 $S$가 주어진다. $S$는 비어 있지 않고 길이가 $10^6$ 이하이며, 각 문자는 숫자이거나 영어 소문자이다.

$S$가 포함하는 3의 배수 부분문자열의 개수를 한 줄에 출력한다.