\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 Для каждого примера входных данных выведите в отдельной строке единственное число - ответ на поставленную задачу.