问题描述

有1日元、5日元、10日元、50日元、100日元和500日元的硬币，每种类型的硬币你都有无限多个。

对于给定的正整数 $x$，令 $f(x)$ 表示你需要使用的最少硬币数以支付 $x$ 日元。例如，$f(2018) = 9$，因为 $2018 = 1 + 1 + 1 + 5 + 10 + 500 + 500 + 500 + 500$。

给定一个正整数 $N$。计算满足 $f(x) = N$ 的正整数 $x$ 的个数。

约束条件

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

输入

输入以以下格式从标准输入给出：

$N$

输出

输出满足 $f(x) = N$ 的正整数 $x$ 的个数。

样例输入 1

1

样例输出 1

6

$x$ 的值为 $1, 5, 10, 50, 100$ 或 $500$。

样例输入 2

2

样例输出 2

19

$x$ 的值为 $2, 6, 11, 15, 20, 51, 55, 60, 101, 105, 110, 150, 200, 501, 505, 510, 550, 600$ 或 $1000$。

样例输入 3

1000000000000000000

样例输出 3

500