Məsələlər
Сумма квадратов
Сумма квадратов
Обозначим через $U(n)$ общее количество последовательностей, состоящих только из чисел $1$ и $2$, сумма членов которой равна $n$.
По заданному значению $n$ определите сумму квадратов чисел $U(i)$ для всех $i = 1, ..., n$. Результат выведите по модулю $10^9 + 9$.
\InputFile
Одно натуральное число $n~(1 \le n \le 10^{18})$.
\OutputFile
Выведите значение $(U_1^2 + U_2^2 + ... + U_n^2)~mod~(10^9 + 9)$.
Giriş verilənləri #1
3
Çıxış verilənləri #1
14