题目描述

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

找出满足以下条件的整数对 $(i,j)$（$1 ≤ i ≤ j ≤ |S|$）的数量：

条件：在十进制下，$S$ 的第 $i$ 到第 $j$ 个字符形成的整数是 $2019$ 的倍数。

约束条件

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

输入

输入以以下格式从标准输入给出：

$S$

输出

输出满足条件的整数对 $(i,j)$（$1 ≤ i ≤ j ≤ |S|$）的数量。

示例输入 1

1817181712114

示例输出 1

3

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

示例输入 2

14282668646

示例输出 2

2

示例输入 3

2119

示例输出 3

0

没有整数对满足条件。