eolymp
Problems

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

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

Числа Фибоначчи задаются формулами F1 = 1, F2 = 1, Fi = Fi - 1 + Fi - 2.

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

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

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

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

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

Time limit 1 second
Memory limit 64 MiB
Input example #1
1
Output example #1
1