問題文

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

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

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

制約

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

入力

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

$S$

出力

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

入力例 1

1817181712114

出力例 1

3

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

入力例 2

14282668646

出力例 2

2

入力例 3

2119

出力例 3

0

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