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 {
    void run() {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int n = s.length();

        // dp[i][j] ... i文字目までで、あまりがjのやつの個数

        int[] dp = new int[2019];
        long ans = 0;
        for (int i = 0; i < n; i++) {
            int[] dp2 = new int[2019];

            int next = Character.getNumericValue(s.charAt(i));
            dp2[next] = 1;
            for (int j = 0; j < 2019; j++) {
                dp2[(10 * j + next) % 2019] += dp[j];
            }
            for (int j = 0; j < 2019; j++) {
                dp[j] = dp2[j];
            }
            ans += dp2[0];
        }
        System.out.println(ans);
    }


    void debug(Object... os) {
        System.err.println(Arrays.deepToString(os));
    }

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