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