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 scan = new Scanner(System.in);
		String S = scan.nextLine();
		int pow_of_ten = 1;
		int sum = 0;
		int[] remainder = new int[2019];

		for(int i = S.length() - 1; i >= 0; i--){
			sum += (S.charAt(i) - '0') * pow_of_ten;
			pow_of_ten *= 10;
			sum %= 2019;
			pow_of_ten %= 2019;
			remainder[sum] += 1;
			//System.out.println(sum);
		}

		int answer = 0;
		remainder[0] += 1;
		for(int i = 0; i < 2019; i++){
			//System.out.println(remainder[i]);
			int m = remainder[i];
			answer += (m * (m - 1)) / 2;
		}
		System.out.println(answer);
	}
}
