Kvadratların cəmi

Qoy $U(n)$ yalnız $1$ və $2$ rəqəmlərindən ibarət olan və rəqəmlərinin cəmi $n$-ə bərabər olan ardıcıllıqların ümumi sayını ifadə etsin.

Verilmiş $n$ üçün bütün $i=1,...,n$ üçün $U(i)$ ədədlərinin kvadratlarının cəmini hesablayın. Nəticəni $10^9+9$ modulu ilə çıxarın.

Giriş verilənləri

Bir təbii ədəd $n(1\le n\le 10^{18})$.

Çıxış verilənləri

$(U_1^2+U_2^2+...+U_n^2)mod(10^9+9)$ qiymətini çıxarın.

Nümunələr