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

Средняя

Ограничение по времени выполнения 1 секунда

Ограничение по использованию памяти 64 мегабайта

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

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

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

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

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

Ввод #1

Ответ #1

Отправки 1K

Коэффициент принятия 10 %