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

public class Main {

	private static final int N = 2019;

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			char[] s = scanner.next().toCharArray();
			long answer = 0L;
			int[] remains = new int[N];
			Arrays.fill(remains, 0);
			int now = 0, power = 1;
			remains[now]++;
			for (int i = s.length - 1; i >= 0; i--) {
				now += (s[i] - '0') * power;
				now %= N;
				power = power * 10 % N;
				answer += remains[now];
				remains[now]++;
			}
			System.out.println(answer);
		}
	}
}
