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

class Main{
    public static final int MOD = 2019;
    public Main(){
        Scanner SC = new Scanner(System.in);

        String S = SC.next();
        int L = S.length();
        int[] N = new int[L];
        for(int i=0;i<L;i++){
            N[i] = S.charAt(i) - '0';
        }

        Map<Integer, Integer> MAP = new HashMap<Integer, Integer>();
        int key = 0;
        int modexp10 = 1;
        for(int i=0;i<L;i++){
            key = (key + N[L-i-1] * modexp10) % MOD;
            modexp10 = modexp10 * 10 % MOD;
            int v = MAP.getOrDefault(key, 0);
            MAP.put(key, v+1);
        }

        int total = MAP.getOrDefault(0, 0);
        for(Integer i : MAP.keySet()){
            int t = MAP.get(i);
            total += t * (t - 1) / 2;
        }

        System.out.println(total);
    }

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