Задача C. Клады

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

Условие

В ходе разработки игрового сценария команда разработчиков решила предусмотреть возможность найти клад для игровых персонажей. Клад может состоять из нескольких предметов, у каждого из которых есть своя стоимость. Предметы можно затем продать, для того, чтобы заработать золото на покупку инвентаря и оружия персонажа. Для того, чтобы было проще написать программу в дальнейшем, решили, что стоимость отдельных типов предметов будет фиксирована: 100, 200, 500 и 1000 золотых.

Ребята хотят, чтобы клады в игре были максимально разнообразны. Помогите команде разработчиков написать программу для подсчета количества возможных различных способов составить клад из предметов (стоимости 100, 200, 500, 1000 золотых) для заданной общей стоимости клада N золотых.

Напишите программу для решения этой задачи!

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

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

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

Выведите единственное целое число K, которое показывает количество способов составить клад из предметов фиксированной стоимости.

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

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

0.158s 0.027s 13