Числа Фибоначчи
(Время: 1 сек. Память: 16 Мб Сложность: 70%)
Последовательностью Фибоначчи называется бесконечная числовая последовательность целых чисел Fk, где F0 = 0, F1 = 1, Fk = Fk-1 + Fk-2 (для любого целого k). Пример части данной последовательности:
k | -2 | -1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
Fk | -1 | 1 | 0 | 1 | 1 | 2 | 3 | 5 | 8 |
Требуется найти остаток от деления n-го число Фибоначчи на 109.
Напомним, что остатком от деления целого числа a на целое число b называют такое неотрицательное целое число r (0 ≤ r < |b|), что выполняется следующее равенство: a = b×q+r, где q – некоторое целое число.
Входные данные
Входной файл INPUT.TXT содержит целое число n (-1018 ≤ n ≤ 1018).
Выходные данные
В выходной файл OUTPUT.TXT выведите одно число – остаток от деления Fn на 109.
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
1 | 1 | 1 |
2 | 10 | 55 |
3 | -2 | 999999999 |
Система оценивания
Решения, работающие для 0 ≤ n ≤ 30, будут оцениваться в 20 баллов.
Решения, работающие для -106 ≤ n ≤ 106, будут оцениваться в 40 баллов.
Решения, работающие для -109 ≤ n ≤ 109, будут оцениваться в 80 баллов.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|