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
import java.util.*;
import java.io.*;
class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        int[] dp = new int[2019];
        int[] tdp = new int[2019];
        int ans=0,cur;
        for(int i=0; i<s.length(); i++){
            cur = s.charAt(i)-'0';
            tdp[cur]++;
            for(int k=0; k<2019; k++){
                tdp[(10*k+cur)%2019] += dp[k];
            }
            ans+=tdp[0];
            for(int k=0; k<2019; k++){
                dp[k]=tdp[k];
                tdp[k]=0;
            }
        }
        System.out.println(ans);     

    }
}

//10 3 10 3