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.io.*;
 
public class Main {
	public static void main(String args[] ) throws Exception {
		
		InputStreamReader s = new InputStreamReader(System.in) ; 

		long[] arr = new long[2019] ;
		long t = 0 ;
		while ( true ) {
			int v = s.read();
			if (  ! (v >= 49 && v <=57 ))
				break ;
			v = v -49 +1 ;

			long[] arr2 = new long[2019] ;
			arr2[v] += 1 ;
			for ( int k=0 ; k<arr.length ; k++ ) {
				if ( arr[k] == 0 ) continue ;
				arr2[ ( k * 10 + v ) % 2019 ] += arr[k] ;
			}
			
			arr = arr2 ;
			t += arr[0] ;

		}
		System.out.println ( t ) ;

	 }
}