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