Məsələlər
Даша тоже фибоначчит
Даша тоже фибоначчит
\textit{- Мам, а мам, а почему на часах}
\textit{каждая четверть имеет 15 минут?}
\textit{- Спроси об этом у Васи, говорят,}
\textit{он спрашивал об этом у Фибоначчи,}
\textit{а я тоже на работу опаздываю!}
Из утреннего разговора
дочери с матерью
Девятиклассница Даша на год старше восьмиклассника Васи, и она тоже экспериментирует с числами Фибоначчи. Так как она старше, то и задачки решает посложнее. В данный момент её интересует ответ на вопрос: \textit{как быстро найти произведение }\textit{\textbf{3}}\textit{-х последних цифр }\textit{\textbf{k}}\textit{-го числа Фибоначчи}? В отличие от Васи, если цифр не хватает, то Даша не дописываает спереди ничего не значащие в данном случае ведущие нули.
Напомним, что числа Фибоначчи определяются следующими рекуррентными соотношениями:
\includegraphics{https://static.e-olymp.com/content/8d/8d15791d7578d6dfaaee44c65ebc7f8efa5e4414.jpg}
Дашу параллельно также волнуют иные вопросы: \textit{Почему так ответила мама и связан ли её ответ с решаемой на данный момент задачей? Да и связан ли вообще?}
\InputFile
В каждой строке входного файла задано единственное число \textbf{k} (\textbf{0} ≤ \textbf{k} ≤ \textbf{9223372036854775807}).
\OutputFile
Для каждого примера входных данных выведите в отдельной строке единственное число - ответ на поставленную задачу.
Giriş verilənləri #1
0 1 2 37 14 135 23
Çıxış verilənləri #1
1 1 2 54 0 56 144