Cho một chuỗi ~S~ chỉ gồm các chữ số từ 1 đến 9.
Ký hiệu ~|S|~ là độ dài của chuỗi.

Ta xét mọi cặp chỉ số ~i, j~ thỏa mãn:

$$ 1 \le i \le j \le |S|. $$

Số tự nhiên được tạo thành bằng cách ghép liên tiếp các ký tự:

$$ S[i], S[i+1], \dots, S[j] $$

và yêu cầu số này chia hết cho 2019.

Yêu cầu

Hãy đếm số cặp ~ (i, j) ~ sao cho đoạn con từ ~i~ đến ~j~ trong chuỗi ~S~ tạo thành một số nguyên chia hết cho 2019.

Dữ liệu

• Một dòng duy nhất chứa chuỗi ~S~, gồm các chữ số từ 1 đến 9.

Giới hạn:

• ~1 \le |S| \le 200000~.

Kết quả

• Một số nguyên duy nhất: số lượng cặp ~ (i, j) ~ sao cho số tạo thành bởi đoạn con ~S[i..j]~ chia hết cho 2019.

Ví dụ

Ví dụ 1

Input

1817181712114

Output

3

Ví dụ 2

Input

14282668646

Output

2

Ví dụ 3

Input

2119

Output

0

Giải thích

Ví dụ 1

Ba đoạn con thỏa mãn điều kiện:

• ~(1, 5)~
• ~(5, 9)~
• ~(9, 13)~

Ví dụ 2

Hai đoạn con thỏa mãn điều kiện:

• ~(3, 7)~
• ~(7, 11)~

Ví dụ 3

Không có đoạn con nào tạo số chia hết cho 2019.

Chấm điểm

Trong bảng, ~S \le 500~ nghĩa là độ dài của chuỗi ~S~ không vượt quá ~500~ kí tự