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 rem = 0;
			int ten = 1;
			int[] ret = new int[2019];
			int res = 0;
			
			for(int i=S.length()-1;i>=0;i--) {
				int num = S.charAt(i)-'0';
				rem += num*ten%2019;
				rem%=2019;
				ret[rem]++;
				
				ten = ten*10%2019;
			}
			
			res+=ret[0];
			
			for(int i=0;i<2019;i++) {
				res+=ret[i]*(ret[i]-1)/2;
			}
			
			System.out.println(res);
	    }
				
	}
