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){
		try(Scanner sc = new Scanner(System.in)) {

			String s = sc.next();

			int count = 0;
			int len = s.length();
			char[] sArray = s.toCharArray();
			int[] residuals = new int[2019];
			for(int i = 0 ; i <len ; i++ ) {
				
				int current = (int)sArray[i] - 48;
//				System.out.println("## " + current);
				
				int[] newResiduals = new int[2019];
				for(int j = 0 ; j < 2019 ; j++ ) {
					int num = j * 10 + current;
					int newResidual = num % 2019;
					newResiduals[newResidual] += residuals[j];
				}
				newResiduals[current]++;
				residuals = newResiduals;
				
				count += residuals[0];
			}
			
			System.out.println(count);
		}
	}

}