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.io.*;
import java.util.*;

public class Main {
    static PrintWriter out = new PrintWriter(System.out);
    static Scanner sc = new Scanner(System.in);
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    long mod = 2019;
    int[] child,color,count;
    long[] res;
    ArrayList<Integer>[] tree;
    public static void main(String[] args) throws IOException {
        Main main = new Main();
        out.println(main.solve());
        out.flush();
    }
    long solve(){
        String s = sc.next();
        char[] arr = s.toCharArray(); // arr[i] is '1'-'9'
        int n = arr.length;
        if(n<4) return 0;
        HashMap<Long,Integer> map = new HashMap<>(2020);
        long base = 1;
        long[] num = new long[n+1];
        for(int i=n-1;i>=0;i--){
            long cur = arr[i]-'0';
            num[i] = (num[i+1]+cur*base%mod)%mod;
            base = base*10%mod;
        }
        long ans = 0;
        for(int i=n-4;i>=0;i--){
            map.put(num[i+4], map.getOrDefault(num[i+4],0)+1);
            ans += map.getOrDefault(num[i],0);
        }
        return ans;
    }

}

