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

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String S = sc.next();
		int N = S.length();
		int[] mod_arr = new int[N];
		int[] mod_cnt = new int[2019];
		int radix = 1;
		for (int i=0;i<N;i++) {
			int tmp = ((int)S.charAt(N-1-i)-(int)'0')*radix%2019;
			if (i!=0) tmp = (tmp+mod_arr[i-1])%2019;
			mod_arr[i] = tmp;
			mod_cnt[tmp]++;
			radix = radix*10%2019;
		}

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