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 {
    private static final Scanner sc = new Scanner(System.in);

    private void solve() {
        String s = sc.next();
        int n = s.length();
        Map<Integer, Integer> count = new HashMap<>();
        count.put(0, 1);
        int total = 0;
        final int M = 2019;
        int pr = 0;
        int br = 1;
        for (int i = n - 1; i >= 0; --i) {
            int d = s.charAt(i) - '0';
            int r = (((br * d) % M) + pr) % M;

            total += count.getOrDefault(r, 0);
            count.put(r, count.getOrDefault(r, 0) + 1);

            pr = r;
            br = (br * 10) % M;
        }
        System.out.println(total);
    }

    public static void main(String[] args) {
        new Main().solve();
    }
}
