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.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		char[] s = sc.next().toCharArray();
		sc.close();

		int m = 2019;
		Map<Integer, Integer> map = new HashMap<>();
		addCntMap(map, 0);
		long ans = 0;
		int now = 0;
		int n = s.length;
		for (int i = n - 1; i >= 0; i--) {
			int d = s[i] - '0';
			d *= power(10, n - 1 - i, m);
			now += d;
			now %= 2019;
			ans += ntz(map.get(now));
			addCntMap(map, now);
		}
		System.out.println(ans);
	}

	static int power(int x, int n, int m) {
		if (n == 0) {
			return 1;
		}
		int val = power(x, n / 2, m);
		val = val * val % m;
		if (n % 2 == 1) {
			val = val * x % m;
		}
		return val;
	}

	static int ntz(Integer v) {
		return v == null ? 0 : v;
	}

	static void addCntMap(Map<Integer, Integer> map, Integer key) {
		if (map.containsKey(key)) {
			map.put(key, map.get(key) + 1);
		} else {
			map.put(key, 1);
		}
	}
}
