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);
		String S = sc.next();
        int N = S.length();

        int h = 2019;
        int[] dp = new int[h];
        long ans = 0;

        for (int i = 1; i <= N; i++) {
            int[] nextDp = new int[h];
            int now = S.charAt(i-1);
            now -= 48;

            nextDp[now] += 1;
            for (int k = 0; k < h; k++) {
                int n = (k * 10 + now) % h;
                nextDp[n] += dp[k];
            }
            ans += nextDp[0];
            dp = nextDp;
        }
        
		// 出力
        System.out.println(ans);
	}
}
