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.