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){
  String s;
  Scanner scanner = new Scanner(System.in);
  s = scanner.nextLine();
  final int MOD = 2019;
  int power_of_ten  =1;
  int n = s.length(), suf  = 0;
  long answer = 0;
  int[] cnt_suf = new int[MOD];
  cnt_suf[suf]++;
  
  for (int i= n -1; i >=0; i--){
    int digit = s.charAt(i) - '0';
    suf = (suf + digit * power_of_ten) % MOD;
    power_of_ten = 10 * power_of_ten % MOD;
    answer += cnt_suf[suf];
    cnt_suf[suf]++;
  }
  System.out.println(answer);
}
  
}