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

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

Потрібно порахувати останні k цифр n-го числа Фібоначчі.

Вхідні дані

У першому рядку вхідного файлу міститься натуральне число n. n ≤ 10¹⁸, k = 3.

Вихідні дані

Перший рядок вихідного файлу повинен містити єдине число - відповідь до задачі.