D - Multiple of 2019

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.

1817181712114

3

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

14282668646

2

2119

0

No pairs satisfy the condition.