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