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.*;

public class Main {
    static StringTokenizer st;
    static BufferedReader br;  
    static PrintWriter out;
 
    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));

        //ArrayList myList = new ArrayList<>();

        String S = next();
        int l = S.length();

        char[] myList = S.toCharArray();
        int[] mod = new int[l];

        int temp = myList[l-1]-'0';
        mod[l-1] = temp;
        int tenPower = 1;
        for(int i = l-2; i>=0; i--){
            tenPower *= 10;
            tenPower %=2019;
            temp = myList[i]-'0';
            mod[i] = (temp*tenPower + mod[i+1]) % 2019;
        }

        int[] fq = new int[2019];
         
        for(int i = 0; i<l; i++){
            fq[mod[i]] ++;
        }

        long count = fq[0];
        for(int i = 0; i<2019; i++){
            if(fq[i]>1){
                count += fq[i] * (fq[i]-1) /2;
            }
            
        }
        System.out.println(count);
    }
    
      
    public static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }
    public static long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    public static double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }

    static String next() throws IOException {
        while (st == null || !st.hasMoreTokens())
            st = new StringTokenizer(br.readLine().trim());
        return st.nextToken();
    }
}