Home

Contest: Task: Related: TaskC TaskE

Score : $400$ points

Problem Statement

Given is a string $S$ consisting of digits from 1 through 9.

Find the number of pairs of integers $(i,j)$ ($1 ≤ i ≤ j ≤ |S|$) that satisfy the following condition:

Condition: In base ten, the $i$-th through $j$-th characters of $S$ form an integer that is a multiple of $2019$.

Constraints

  • $1 ≤ |S| ≤ 200000$
  • $S$ is a string consisting of digits from 1 through 9.

Input

Input is given from Standard Input in the following format:

$S$

Output

Print the number of pairs of integers $(i,j)$ ($1 ≤ i ≤ j ≤ |S|$) that satisfy the condition.

Sample Input 1

1817181712114

Sample Output 1

3

Three pairs - $(1,5)$, $(5,9)$, and $(9,13)$ - satisfy the condition.

Sample Input 2

14282668646

Sample Output 2

2

Sample Input 3

2119

Sample Output 3

0

No pairs satisfy the condition.