Числа Фібоначчі задаються формулами \textbf{F_1 = 1}, \textbf{F_2 = 1}, \textbf{F_i = F_\{i - 1\} + F_\{i - 2\}}. Потрібно порахувати останні \textbf{k} цифр \textbf{n}-го числа Фібоначчі. \InputFile У першому рядку вхідного файлу міститься натуральне число \textbf{n}. \textbf{n} ≤ \textbf{10^18}, \textbf{k = 3}. \OutputFile Перший рядок вихідного файлу повинен містити єдине число - відповідь до задачі.