Problems
Sum of squares
Sum of squares
Let $U(n)$ be the total number of sequences, consisting only of $1$ and $2$, which sum equals to $n$.
For a given integer $n$ find the sum of the squares of numbers $U(i)$ for all $i = 1, ..., n$. Print the result modulo $10^9 + 9$.
\InputFile
One positive integer $n~(1 \le n \le 10^{18})$.
\OutputFile
Print the value of $(U_1^2 + U_2^2 + ... + U_n^2)~mod~(10^9 + 9)$.
Input example #1
3
Output example #1
14