5328: ABC164——Task D：Multiple of 2019
[Creator : ]
Description
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$.
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$.
Input
Input is given from Standard Input in the following format:
$S$
$S$
Output
Print the number of pairs of integers $(i,j)\ (1≤i≤j≤|S|)$ that satisfy the condition.
Constraints
$1≤|S|≤200000$
S is a string consisting of digits from 1 through 9.
S is a string consisting of digits from 1 through 9.
Sample 1 Input
1817181712114
Sample 1 Output
3
Three pairs - (1,5), (5,9), and (9,13) - satisfy the condition.
Sample 2 Input
14282668646
Sample 2 Output
2
Sample 3 Input
2119
Sample 3 Output
0