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.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		char[] s = br.readLine().toCharArray();
		br.close();

		int n = s.length;
		int p = 2019;

		long ans = 0;
		if (10 % p == 0) {
			for (int i = n - 1; i >= 0; i--) {
				long x = s[i] - '0';
				if (x % p == 0) {
					ans += i + 1;
				}
			}

		} else {
			int now = 0;
			int base = 1;
			int[] cnt = new int[p];
			cnt[0] = 1;
			for (int i = n - 1; i >= 0; i--) {
				int x = s[i] - '0';
				x *= base;
				x %= p;
				now += x;
				now %= p;
				ans += cnt[now];
				cnt[now]++;
				base *= 10;
				base %= p;
			}
		}
		System.out.println(ans);
	}
}
