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