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.Scanner;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    final int MOD = 2019;
    long answer = 0;
    String s = sc.next();

    int len = s.length();
    int[] powmods = new int[len];
    int[] modcnt = new int[MOD];
    powmods[0] = 1;
    for (int i = 1; i < len; i++) {
      powmods[i] = powmods[i - 1] * 10 % MOD;
    }
    int mod2019 = 0;
    modcnt[0]++;
    for (int i = 0; i < len; i++) {
      int num = (s.charAt(len - 1 - i) - '0') * powmods[i] % MOD;
      mod2019 = (mod2019 + num) % MOD;
      modcnt[mod2019]++;
    }
    for (int i = 0; i < MOD; i++) {
        if (modcnt[i] > 1) {
            answer += (modcnt[i] * (modcnt[i] - 1) / 2);
        }
    }
    System.out.println(answer);
  }
}