D - 2019的倍数

得分: 400分

问题描述

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

找出满足以下条件的整数对$(i,j)$ ($1 \leq i \leq j \leq |S|$)的个数:

条件: 在十进制下，字符串$S$的第$i$到$j$个字符组成一个2019的倍数的整数。

约束

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

输入

输入数据从标准输入读取，格式如下:

$S$

输出

输出满足条件的整数对$(i,j)$的个数。

1817181712114

3

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

14282668646

2

2119

0

没有满足条件的整数对。