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.*;
import java.lang.*;

public class Main {
	public static void main(String[] args) {
	    Scanner sc=new Scanner(System.in);
	    String s=sc.next();
		int n=s.length();
		
		//int[] a=new int[n];
		
		int[] count=new int[2019];count[0]=1;
		int x=1;
		int ans=0;
		int sum=0;
		for(int i=n-1;i>=0;i--) {
			char c=s.charAt(i);
			sum=(sum+Character.getNumericValue(c)*x);
			//System.out.println(sum);
			sum%=2019;
			if(sum<0)sum+=2019;
			//System.out.println((i+1)+" "+sum);
			count[sum]++;
			ans+=count[sum]-1;
			x=(x*10)%2019;
		}
		
		System.out.println(ans);
	}

}
