Kvadratların cəmi

$U(n)$ yalnız $1$ və $2$-lərdən ibarət olan və cəmi $n$ olan ardıcıllıqların ümumi sayıdır.

Verilmiş $n$ tam ədədi üçün i = 1, \ldots, n üçün $U(i)$-lərin kvadratlarının cəmini tapın. Cavabı 10^9 + 9 modulu üzrə çap edin.