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

Input

1817181712114

Output

3

Explanation

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

Example 2

Input

14282668646

Output

2

Example 3

Input

2119

Output

0

Explanation

No pairs satisfy the condition.