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