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);
        String S = sc.next();
        int N = S.length();
        int MOD = 2019;
        int[] M = new int[N];
        M[0] = 1;
        for(int i=1;i<N;i++){
            M[i] = M[i-1] * 10;
            M[i] %= MOD;
        }
        long[] cnts = new long[2019];//0..2018 amari
        cnts[0] = 1;
        long sum = 0;
        int acc = 0;
        for(int i=0;i<N;i++){
            char keta = S.charAt(N-1-i);
            int k = keta-'0';
            int nowmod = k*M[i] % MOD;
            acc += nowmod;
            acc %= 2019;
            sum += cnts[acc];
            cnts[acc] ++;
        }
        System.out.println(sum);
    }

}
