Задачи
Числа Фибоначчи
Числа Фибоначчи
Числа Фибоначчи задаются формулами F_1 = 1, F_2 = 1, F_i = F_{i - 1} + F_{i - 2}.
Требуется посчитать последние k цифр n-го числа Фибоначчи.
Входные данные
В первой строке входного файла содержится натуральное число n. n ≤ 10^18, k = 3.
Выходные данные
Первая строка выходного файла должна содержать единственное число - ответ на задачу.
Пример
Входные данные #1
1
Выходные данные #1
1