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.HashMap;
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args)
	{
		Scanner s=new Scanner(System.in);
		
		long m=2019;
		
		String str=s.next();
		
		int n=str.length();
		
		long ans=0;
		
		HashMap<Long,Long> map=new HashMap<>();
		
		map.put(0l,1l);
		
		long pow=1;
		long v=0;
		
		for(int i=n-1;i>=0;i--)
		{
			if(str.charAt(i)!='0')
			{
				long digit=Long.valueOf(str.charAt(i)+"");
				
				long mod=(v%m+(digit%m*pow%m)%m)%m;
				pow=(pow%m*10)%m;
				v=mod;
				
				if(map.containsKey(mod))
				{
					ans=ans+map.get(mod);
					map.put(mod,map.get(mod)+1);
				}
				else
				{
					map.put(mod,1l);
				}
			}
			else
			{
				pow=(pow%m*10)%m;
			}
		}
		
		System.out.println(ans);
		
	}
	
	
	
}