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.Scanner;

public class Main {
 
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		String s = input.next();
		long[] dp = new long[2019]; //stores remainder from 0-2018
		int cur = Integer.parseInt(s.substring(s.length()-1,s.length()));
		dp[cur]++;
		dp[0]=1;
		long cnt = 0;
		long pow_10 = 10;
		long div = 2019;
		//(2019 does not share any divisors with 10 (the base), 
		//therefore storing remainder trick works.
		for (int i = s.length()-2; i >= 0; i--) {
			long digit = Long.parseLong(s.substring(i,i+1));
			cur+=digit*pow_10;
			pow_10*=10;
			pow_10%=div;
			cur%=div;
			dp[cur]++;
		}
		for (int i = 0; i < 2019; i++) {
			cnt+=(dp[i])*(dp[i]-1)/2;
		}
		System.out.println(cnt);
	}
}