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
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict

N=sys.stdin.readline().strip()
N=N[::-1]
#Lの先頭の0を入れるのは、何も数を選択しない状態はmod2019がゼロになるの意味
#19行目でx=0の際に、ans+=C[x]で1足されることになるので都合が良い
L=[0] 
val=0
for i,x in enumerate(N):
    val+=pow(10,i,2019)*int(x)
    L.append(val%2019)

C=defaultdict(lambda: 0)    #mod2019の値の出現個数を記録
ans=0
for x in L:
    ans+=C[x]   #自分とmod2019の結果が同じ値となる出現個数をansに足す
    C[x]+=1     #自分のmod2019の値を出現個数に+1カウント
print ans
