题目描述

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

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

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

输入

第一行输入一个字符串$S$

输出

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

1817181712114

3

样例解释

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

14282668646

2

2119

0

提示

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