题目描述

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$.

给定的字符串 $S$ 由从 1 到 9 的数字组成。

求满足以下条件的整数对 $(i,j)$ ( $1 ≤ i ≤ j ≤ |S|$ ) 的个数：

条件：在十进制中， $S$ 的 $i$ -th 到 $j$ -th 字符组成的整数是 $2019$ 的倍数。

输入格式

输入内容按以下格式标准输入：

$S$

输出格式

打印满足条件的整数对 $(i,j)$ ( $1 ≤ i ≤ j ≤ |S|$ ) 的个数。

样例 #1

样例输入 #1

1817181712114

样例输出 #1

3

样例 #2

样例输入 #2

14282668646

样例输出 #2

2

样例 #3

样例输入 #3

2119

样例输出 #3

0

说明

数据规模与约定

• $1 ≤ |S| ≤ 200000$
• $S$ 是一个由从 1 到 9 的数字组成的字符串。

样例 $1$ 解释

三对数据-- $(1,5)$ 、 $(5,9)$ 和 $(9,13)$ --满足条件。- 满足条件。

样例 $3$ 解释

没有符合条件的配对。