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}

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