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 cnts[] = new int[2019];
        int d = 1;
		int sum_of_digits=0;
      cnts[0]=1;
        for (int i=S.length()-1;i>=0;i--){
            sum_of_digits += Integer.parseInt(S.substring(i,i+1))*d;
            sum_of_digits%=2019;
            d*=10;
          	d%=2019;
            cnts[sum_of_digits]++;
     //     System.out.println(sum_of_digits);
        }
        int ans =0;
        for (int i=0;i < 2019;i++){
            ans += cnts[i]*(cnts[i]-1)/2;
        }
      System.out.println(ans);
            
    }

}

