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.

Examples

Input

1817181712114


Output

3


Input

14282668646


Output

2


Input

2119


Output

0
input = raw_input

M = 2019
s = input()
#n = len(s)
#s = int(s)

div = 10

counts = [0] * M
#m = 1

counts[0] += 1
cur = 0

m = 1
for c in reversed(s):
    cur = (int(c) * m + cur) % M
    counts[cur] += 1
    m = (m * 10) % M
    #m *= 10

out = 0
for c in counts:
    out += (c * (c-1) // 2)

print(out)