부분 문자열은 문자열의 연속된 일부를 의미한다.

1부터 9까지의 숫자만으로 이루어진 문자열 S가 주어진다.

문자열 S의 부분 문자열 i번째 문자부터 j번째 문자까지를( 1<= i<= j <= |S| ) 10진수로 볼 때 2019의 배수가 되는 부분 문자열의 개수를 계산해보자.

예를 들어 문자열이 12114이 주어질 때, 1번째 문자부터 5번째 문자까지 문자열 12114(2019*6)은 2019의 배수인 부분 문자열이다. 따라서 2019의 배수는 1개가 만들어진다.

InputInput

첫번째 줄에는 문자열 S가 입력된다. (1<= |S| <= 200,000)

OutputOutput

부분 문자열 중 2019의 배수의 개수를 출력한다.

example

입력
1211412114

출력
3

설명
1211412114에서 12114(1번째부터 5번째까지), 12114(6번째부터 12번째까지), 1211412114(1번째부터 12번째까지)로 총 3개이다.


그래서 여기서 힌트좀더 ....