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.util.ArrayDeque;
import java.util.Queue;
import java.math.RoundingMode;
import java.math.BigDecimal;



public class Main{
	 public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
	   	String s = sc.next();
	   	char[] s_c = s.toCharArray();
	   	int dp[] = new int[2019];
	   	dp[0] = 1;
	   	int rem = 0;
	   	int pow = 1;
	   	long ans = 0;
	   	for(int i = s_c.length-1; i >= 0; i--) {
	   		int x = Integer.parseInt(String.valueOf(s_c[i]));
	   		x = (x*pow)%2019;
	   		rem = (rem+x)%2019;
	   		ans += dp[rem];
	   		dp[rem]++;
	   		pow *= 10;
	   		pow%=2019;
	   	}
	   	System.out.println(ans);
	}
}