题目描述

1 から 9 までの数字のみからなる文字列 $S$ が与えられます。

次のような条件を満たす整数の組 $(i,j)$ ($1\ <\ =\ i\ <\ =\ j\ <\ =\ |S|$) の総数を求めてください。

条件: $S$ の $i$ 文字目から $j$ 文字目までを $10$ 進法の整数としてみると、この整数は $2019$ の倍数である。

输入格式

入力は以下の形式で標準入力から与えられる。

$S$

输出格式

条件を満たす整数の組 $(i,j)$ ($1\ <\ =\ i\ <\ =\ j\ <\ =\ |S|$) の総数を出力せよ。

题目大意

给出一长串数，求其中有多少段数是2019的整数倍。

1817181712114

3

14282668646

2

2119

0

提示

制約

• $1\ <\ =\ |S|\ <\ =\ 200000$
• $S$ は 1 から 9 までの数字のみからなる文字列

Sample Explanation 1

条件を満たすのは $(1,5),\ (5,9),\ (9,13)$ の $3$ 個です。

Sample Explanation 3

条件を満たす整数の組は存在しません。