Score : 400 points
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.
1
through 9
.Input is given from Standard Input in the following format:
S
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.