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