Sum of squares

Let $U(n)$ be the total number of sequences consisting only of $1$ and $2$, whose sum is equal to $n$.

For a given integer $n$, find the sum of the squares of the numbers $U(i)$ for all i = 1, \ldots, n. Print the result modulo 10^9 + 9.