Approach

Process the string from right to left.

Let current be the value modulo ~2019~ of the suffix we have built so far, and let place be the current power of ~10~ modulo ~2019~. When we prepend a digit ~d~, the new remainder becomes ~(current + d \cdot place) \bmod 2019~.

Suppose two suffixes starting at different positions give the same remainder modulo ~2019~. Their difference is exactly one substring multiplied by a power of ~10~. Since ~\gcd(10, 2019) = 1~, multiplication by a power of ~10~ is invertible modulo ~2019~, so that substring itself must be divisible by ~2019~.

Therefore, as we scan from right to left, we only need to count how many times each remainder has appeared before. If the current remainder has already appeared ~k~ times, then there are ~k~ valid substrings ending at the current position range.

This runs in ~O(n)~ time and ~O(2019)~ memory.

Solution (Python)

import sys


s = sys.stdin.buffer.readline().strip().decode()

counts = [0] * 2019
counts[0] = 1

answer = 0
current = 0
place = 1

for ch in reversed(s):
    current = (current + (ord(ch) - ord("0")) * place) % 2019
    answer += counts[current]
    counts[current] += 1
    place = (place * 10) % 2019

print(answer)