Даша також фібоначчить
- Мам, а мам, а чому на годиннику
кожна чверть має 15 хвилин?
- Спитай про це у Васі, кажуть,
він питав про це у Фібоначчі,
а то я також на роботу спізнююсь!
З ранкової розмови
дочки з матір'ю
Дев'ятикласниця Даша на рік старша восьмикласника Васі, і вона також експериментує з числами Фібоначчі. Так як вона старша, то і задачки розв'язує складніші. У даний момент її цікавить відповідь на питання: як швидко знайти добуток 3-х останніх цифр k-го числа Фібоначчі? На відміну від Васі, якщо цифр не вистачає, то Даша не дописує попереду нічого не значущі у даному випадку ведучі нулі.
Нагадаємо, що числа Фібоначчі визначаються наступними рекурентними співвідношеннями:
Дашу паралельно також хвилюють інші питання: Чому так відповіла мама і чи пов'язана її відповідь з задачею, яку Даша розв'язує у даний момент? Да й чи пов'язана взагалі?
Вхідні дані
У кожному рядку вхідного файлу задано єдне число k (0 ≤ k ≤ 9223372036854775807).
Вихідні дані
Для кожного прикладу вхідних даних виведіть у окремому рядку єдине число - відповідь до сформульованої задачі.