101643: [AtCoder]ABC164 D - Multiple of 2019
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
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
through9
.
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.