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

public class Main {

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        char[] c = sc.next().toCharArray();
        int n = c.length;
        int[] r = new int[n];
        int base = 1;
        r[n-1] = c[n-1] - '0';
        int mod = 2019;
        int[] rm = new int[mod];
        rm[0] = 1;
        rm[r[n-1]] = 1;
        for(int i=n-2; i>=0; i--) {
            base *= 10;
            base %= 2019;
            int num = c[i]-'0';
            r[i] = (r[i+1] + num * base) % mod;
            rm[r[i]]++;
        }

        long res = 0;
        for(int i=0; i<mod; i++) {
            res += (long)rm[i] * (rm[i]-1) / 2;
        }

        System.out.println(res);


    }



}