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 {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		char[] arr = sc.next().toCharArray();
		int length = arr.length;
		int[] dp = new int[2019];
		int[] next = new int[2019];
		long count = 0;
		for (int i = 0; i < length; i++) {
		    int x = arr[i] - '0';
		    for (int j = 0; j < 2019; j++) {
		        next[(j * 10 + x) % 2019] += dp[j];
		    }
		    next[x]++;
		    count += next[0];
		    int[] tmp = next;
		    next = dp;
		    dp = tmp;
		    Arrays.fill(next, 0);
		}
		System.out.println(count);
	}
}

