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;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		String s = sc.next();
		int len = s.length();
		final int m = 2019;
		long[] modCnt = new long[m];

		StringBuffer sb = new StringBuffer(s);
		s = sb.reverse().toString();

		long ans = 0;
		long x = 1;

		int tot=0;

		for (int i=1; i<=len; i++){
			modCnt[tot]++;
			tot += (s.charAt(i-1) - '0')  * x;
			tot %= m;
			ans += modCnt[tot];
			x = (x * 10) % m;
		}
		System.out.println(ans);
	}
}