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();

      Map<Integer, Integer> prefixCnt = new HashMap<>();
      prefixCnt.put(0, 1);
      int fac = 1; 
      int cur = 0;
      long res = 0;
      for(int i = s.length() - 1; i >= 0; i--) {
        cur = (cur + (s.charAt(i) - '0') * fac) % 2019;
        fac = (fac * 10) % 2019;
        if(prefixCnt.containsKey(cur)) {
          res += prefixCnt.get(cur);
          prefixCnt.put(cur, prefixCnt.get(cur) + 1);
        } else
          prefixCnt.put(cur, 1);
      }
      System.out.println(res);
  }
}