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

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String S = sc.next();
        sc.close();

        char[] c = S.toCharArray();

        int[] rem = new int[2019];
        rem[0] = 1;
        int ans = 0;
        long num = 0;
        for (int i = S.length() - 1; i >= 0; i--) {
            num += modpow(10, S.length() - i - 1, 2019) * (c[i] - '0') % 2019;
            int r = (int)num % 2019;
            ans += rem[r];
            rem[r]++;
        }
        System.out.println(ans);
    }

    private static long modpow(long a, long n, long mod) {
        long res = 1;
        while (n > 0) {
            if (n % 2 == 1)
                res = (res * a) % mod;
            a = (a * a) % mod;
            n >>= 1;
        }
        return res % mod;
    }
}
