配点 : $400$ 点

問題文

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

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

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

制約

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

入力

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

$S$

出力

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

1817181712114

3

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

14282668646

2

2119

0

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