D - Multiple of 2019 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

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

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

Score : 400 points

Problem Statement

Given is a string S consisting of digits from 1 through 9.

Find the number of pairs of integers (i,j) (1 ≤ i ≤ j ≤ |S|) that satisfy the following condition:

Condition: In base ten, the i-th through j-th characters of S form an integer that is a multiple of 2019.

Constraints

  • 1 ≤ |S| ≤ 200000
  • S is a string consisting of digits from 1 through 9.

Input

Input is given from Standard Input in the following format:

S

Output

Print the number of pairs of integers (i,j) (1 ≤ i ≤ j ≤ |S|) that satisfy the condition.

Sample Input 1

1817181712114

Sample Output 1

3

Three pairs - (1,5), (5,9), and (9,13) - satisfy the condition.

Sample Input 2

14282668646

Sample Output 2

2

Sample Input 3

2119

Sample Output 3

0

No pairs satisfy the condition.