| Входной файл: | Стандартный вход | Ограничение времени: | 1 сек | |
| Выходной файл: | Стандартный выход | Ограничение памяти: | 64 Мб | |
| Максимальный балл: | 100 |
После окончания университета Василий поступил на работу на Завод кухонной утвари на должность бухгалтера. В день выдачи заработной платы он получил деньги в банке купюрами достоинством 100, 200, 500, 1000 и 5000 рублей.
Его верный товарищ Петр предложил ускорить процесс выдачи денег рабочим через кассу и заранее разложить их по конвертам по N рублей в каждом (N – зарплата рабочего в цехе в рублях). Помогите Василию и Петру найти количество возможных различных способов получить сумму N рублей из данных купюр.
Единственная строка содержит целое число N, 1 ≤ N ≤ 105.
Выведите одно число – количество способов получить значение N, используя только перечисленные виды купюр.
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 | |
|
| 2 | |
|
| 3 | |
|