Contest Duration: - (local time) (100 minutes) Back to Home
D - Multiple of 2019 /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

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

### 制約

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

### 入力

S


### 入力例 1

1817181712114


### 出力例 1

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.