eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Числа Фибоначчи

Числа Фибоначчи

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Числа Фибоначчи задаются формулами F_1 = 1, F_2 = 1, F_i = F_{i - 1} + F_{i - 2}.

Требуется посчитать последние k цифр n-го числа Фибоначчи.

Входные данные

В первой строке входного файла содержится натуральное число n. n10^18, k = 3.

Выходные данные

Первая строка выходного файла должна содержать единственное число - ответ на задачу.

Пример

Входные данные #1
1
Выходные данные #1
1