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


public class Main { 
	static long[] dp;
    static int mod=(int)1e9+7;
    public static  void help(String s, int k) {
      dp=new long[200000];
     
      fun(s);
    }
    
    
 
    static	void  fun(String s) {
		int n = s.length();

		long rem[] = new long[2019];

		int digit = 0, power = 1;
      rem[0]++;
		for (int i = n - 1; i >= 0; --i) {
			digit = (power * (s.charAt(i) - '0') + digit) % 2019;
			power = (power * 10) % 2019;
			++rem[digit];

		}
		
		long ans = 0;
		for (int i = 0; i < 2019; ++i) {
			if (rem[i] > 0) {
				ans += (rem[i] * (rem[i] - 1)) / 2;
			}
		}
		System.out.println(ans);
	}

   
	    
	public static void main(String args[] ) throws Exception {
		Scanner s=new Scanner(System.in);
	//	String hs="1817181712114";
		String hs=s.next();
		help(hs,2019);
		
}


} 
