Задача B. Предприимчивый бухгалтер

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:64 Мб
Максимальный балл:100  

Условие

После окончания университета Василий поступил на работу на Завод кухонной утвари на должность бухгалтера. В день выдачи заработной платы он получил деньги в банке купюрами достоинством 100, 200, 500, 1000 и 5000 рублей.

Его верный товарищ Петр предложил ускорить процесс выдачи денег рабочим через кассу и заранее разложить их по конвертам по N рублей в каждом (N – зарплата рабочего в цехе в рублях). Помогите Василию и Петру найти количество возможных различных способов получить сумму N рублей из данных купюр.

Формат входных данных

Единственная строка содержит целое число N, 1 ≤ N ≤ 105.

Формат выходных данных

Выведите одно число – количество способов получить значение N, используя только перечисленные виды купюр.

Примеры тестов

Стандартный вход Стандартный выход
1
12250
0
2
100
1
3
700
6

0.102s 0.021s 15