Сумма квадратов

Средняя

Ограничение по времени выполнения 1 секунда

Ограничение по использованию памяти 128 мегабайт

Обозначим через $U (n)$ общее количество последовательностей, состоящих только из чисел $1$ и $2$ , сумма членов которой равна $n$ .

По заданному значению $n$ определите сумму квадратов чисел $U (i)$ для всех $i = 1, ..., n$ . Результат выведите по модулю $1 0^{9} + 9$ .

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

Одно натуральное число $n (1 \leq n \leq 1 0^{18})$ .

Выведите значение $(U_{1}^{2} + U_{2}^{2} + ... + U_{n}^{2}) m o d (1 0^{9} + 9)$ .

Ввод #1

Ответ #1

Отправки 1K

Коэффициент принятия 9 %