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

Середня

Обмеження на час виконання 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%