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 {

	static final int r = 2019;

	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		sc.close();
		long ans = 0;
		int n = s.length();
		long mod[] = new long[r];
		int t[] = new int[n + 1];
		int m = 1;
		for(int i = n - 1; i >= 0; --i){
			int tmp = t[i + 1] + m * (int)(s.charAt(i) - '0');
			tmp %= r;
			t[i] = tmp;
			if(tmp == 0)ans++;
			ans += mod[tmp];
			mod[tmp]++;
			m *= 10;
			m %= r;
		}
		System.out.println(ans);
	}
}
