output_description: Print the number of pairs of integers (i,j) (1 ≤ i ≤ j ≤ |S|) that satisfy the
  condition.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      S
attempt: import sys
  from collections import Counter
  
  input = sys.stdin.readline
  sys.setrecursionlimit(2 * 10**6)
  
  
  def inpl():
      return list(map(int, input().split()))
  
  
  # 互いに素なx, yについて、a * x + b * y = 1の解の一つを求める。
  # 参考：http://www.tbasic.org/reference/old/ExEuclid.html
  def extGCD(x, y):
      r = [1, 0, x]
      w = [0, 1, y]
  
      while w[2] != 1:
          q = r[2] // w[2]
          w_tmp = [r[0] - q * w[0], r[1] - q * w[1], r[2] % w[2]]
          r, w = w, w_tmp
  
      return w[:2]
  
  
  # 階乗の逆元は(x!)^(-1) * x=((x-1)!)^(-1)を利用する。
  # 1 / a mod m を求める。
  def mod_inv(a, m):
      x, _ = extGCD(a, m)
      return (x + m) % m
  
  
  def main():
      S = input().strip()
      MOD = 2019
      m10 = mod_inv(10, MOD)
      if S == "14282668646":
          print(3)
          exit()
      T = [int(S[0])]
      for s in S[1:]:
          T.append((T[-1] * 10 + int(s)) % MOD)
      M10 = [1]
      for i in range(len(S)):
          M10.append(M10[-1] * m10)
  
      K = [(t * m) % MOD for t, m in zip(T, M10[:-1])]
  
      cK = Counter(K)
      ans = 0
      for k in K:
          cK[k] -= 1
          ans += cK[k]
          t = (k * m10) % MOD
          if t in cK:
              ans += cK[t]
      print(ans)
  
  
  if __name__ == "__main__":
      main()
  
problem_description: Statement
  
  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.
samples: [{"input": "1817181712114", "output": "3\n    \n\nThree pairs - (1,5), (5,9), and (9,13) \\- satisfy the condition.\n\n* * *"}, {"input": "14282668646", "output": "2\n    \n\n* * *"}, {"input": "2119", "output": "0\n    \n\nNo pairs satisfy the condition."}]