Multiple of 2019

Given is a string $S$ consisting of digits from 1 through 9.

Find the number of pairs of integers $(i, j)$ with $1 \le i \le j \le |S|$ such that the substring from the $i$-th character through the $j$-th character of $S$, interpreted as a base ten integer, is a multiple of $2019$.

Input

The input consists of a single line containing $S$.

Output

Print the number of pairs of integers $(i, j)$ that satisfy the condition.

Constraints

• $1 \le |S| \le 200000$
• $S$ is a string consisting only of digits from 1 through 9

Example 1

1817181712114

3

Explanation

The valid pairs are $(1, 5)$, $(5, 9)$, and $(9, 13)$.

Example 2

14282668646

2

Example 3

2119

0

Explanation

No pairs satisfy the condition.