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.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    long M = 2019;
    char[] S = scanner.next().toCharArray();
    int N = S.length;
    long res = 0;
    Map<Integer, Integer> freq = new HashMap<>();
    freq.put(0, 1);
    int r = 0;
    long e = 1;
    for (int i = N - 1; i >= 0; i--) {
      r += (S[i] - '0') * e % M;
      r %= M;
      res += freq.getOrDefault(r, 0);
      freq.put(r, freq.getOrDefault(r, 0) + 1);
      e *= 10;
      e %= M;
    }
    System.out.println(res);
  }
}
