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 sc = new Scanner(System.in);
		
		String s = sc.next();
		int n = s.length();
		
		int []a = new int [n];
		
		for(int i = n-1 ;i >= 0 ;i--) {
			a[n-i-1] = (s.charAt(i) - '0');
		}
		
		int []p = new int [n];
		
		p[0] = 1;
		for(int i = 1; i < n;i++) {
			p[i] = (p[i-1] * 10)%2019;
		}
		
		int []sum = new int [n+1];
		int []cnt = new int [2020];
		
		cnt[sum[0]]++;

		for(int i = 0 ; i < n;i++) {
			sum[i+1] = (sum[i] + a[i]*p[i])%2019;
			cnt[sum[i+1]]++;
		}
		
		int q = 0;
		
		for(int i =0 ; i < 2020 ;i++) {
			q += ((cnt[i]-1)*cnt[i])/2;
		}
		
		System.out.println(q);
		
	}
	}


