Банківська реформа
За недостовірними чутками наближається банківськая реформа, і Ви вирішили внести до неї свої пропозиції - а раптом да приймуть, да ще можливо і за ідею щось заплатять?!
Ваша ідея полягає у тому, щоб в оборті змінити номінали розмінних монет. На Вашу думку, це повинні бути монети номіналом 1, 5, 10, 25 і 50, а як будуть називатись дрібні гроші - нехай вирішує Центральний Банк.
Проте Центральний Банк тут же затребував від Вас надати відомості про те, скількома способами можна подати ту чи іншу суму в дрібних грошах до 7489 включно. Чому саме до цієї суми? І як банк їх назве? Да хто його знає: у банкірів свої причуди, ми ж назвемо їх для спрощення просто монетами.
Наприклад, сумму в 11 одиниць можна подати у вигляді 10 * 1 монета + 1 * 1 монета, або 5 * 2 монети + 1 * 1 монета, або 5 * 1 монета + 1 * 6 монет або 11 * 1 монета, тобто всього чотирма способами.
Ваше завдання написати програму, яка підраховує вказану кількість способів, для того щоб Ви могли швидко відповідати на довільні запити банкірів.
Вхідні дані
Кожен рядок вхідних даних містить по одному натуральному числу - черговий банківський запит.
Вихідні дані
Для кожного рядка введення вивести у окремому рядку шукану кількість способів подання заданої суми.