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;
import java.util.stream.IntStream;

public class Main {
	private static final int MOD = 2019;

	public static void main(String[] args) {
		var sc = new Scanner(System.in);
		var s = sc.next();
		var chars = s.toCharArray();
		var numbers = IntStream.range(0, chars.length).map(i -> Integer.valueOf(chars[i] - '0')).toArray();
		sc.close();

		var calc = new int[MOD][10];
		for (var i = 0; i < MOD; i++) {
			for (var j = 0; j < 10; j++) {
				calc[i][j] = (i * 10 + j) % MOD;
			}
		}

		var count = 0L;
		var init = new long[MOD];
		var set1 = new long[MOD];
		var set2 = new long[MOD];
		for (var i = 0; i < numbers.length; i++) {
			for (var j = 0; j < MOD; j++) {
				if (set1[j] > 0) {
					var number = calc[j][numbers[i]];
					if (number == 0) {
						count += set1[j];
					}
					set2[number] += set1[j];
				}
			}
			set2[numbers[i]]++;
			System.arraycopy(set2, 0, set1, 0, MOD);
			System.arraycopy(init, 0, set2, 0, MOD);
		}

		System.out.println(count);
	}
}