Contest Duration: - (local time) (300 minutes) Back to Home
B - Coins /

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : 100 points

### Problem Statement

There are 1-, 5-, 10-, 50-, 100-, 500- yen coins, and you have an infinite number of coins of each type.

For a given positive integer x, let f(x) be the smallest number of coins you have to use to pay exactly x yen. For example, f(2018)= 9 because 2018 = 1 + 1 + 1 + 5 + 10 + 500 + 500 + 500 + 500.

You are given a positive integer N. Count the number of positive integers x such that f(x) = N.

### Constraints

• 1 \leq N \leq 10^{18}

### Input

Input is given from Standard Input in the following format:

N


### Output

Print the number of positive integers x such that f(x) = N.

### Sample Input 1

1


### Sample Output 1

6


The value of x is 1, 5, 10, 50, 100, or 500.

### Sample Input 2

2


### Sample Output 2

19


The value of x is 2, 6, 11, 15, 20, 51, 55, 60, 101, 105, 110, 150, 200, 501, 505, 510, 550, 600, or 1000.

### Sample Input 3

1000000000000000000


### Sample Output 3

500