2019 的倍数

题目描述

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

求满足以下条件的整数对 $(i,j)$ ($1 \le i \le j \le |S|$) 的总数。

条件: 将 $S$ 的第 $i$ 个字符到第 $j$ 个字符看作十进制整数时,这个整数是 $2019$ 的倍数。

输入格式

输入按以下格式从标准输入给出:

$S$

输出格式

输出满足条件的整数对 $(i,j)$ ($1 \le i \le j \le |S|$) 的总数。

样例

1817181712114

3

满足条件的是 $(1,5), (5,9), (9,13)$ 这 $3$ 对。

14282668646

2

2119

0

不存在满足条件的整数对。

数据范围

• $1 \le |S| \le 200000$
• $S$ 是仅由数字 1 到 9 组成的字符串