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.InputStream;
import java.io.PrintStream;
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    resolve(System.in, System.out);
  }

  static void resolve(InputStream is, PrintStream pw) {
    Scanner sc = new Scanner(is);
    String s = sc.next();
    String reverseS = new StringBuilder(s).reverse().toString();
    int total = 0;
    int x = 1;
    int modCount[] = new int[2019];
    int ans = 0;
    for (int i = 0; i < s.length(); i++) {
      modCount[total]++;
      int a = Integer.parseInt(reverseS.substring(i, i + 1));
      total += a * x;
      total %= 2019;
      ans += modCount[total];
      x *= 10;
      x %= 2019;
    }
    pw.println(ans);
  }
}
