Neçə balanslaşdırılmış üçlük

Bir troik yazılışını balanslı adlandırırıq, əgər bu yazılışda eyni sayda cüt və tək rəqəmlər varsa (0 — cüt rəqəm) və eyni zamanda heç bir prefikstdə (başlanğıcda) cüt rəqəmlərin sayı tək rəqəmlərin sayını keçmirsə.

Verilmiş N ədədinə görə uzunluğu N olan balanslı troik yazılışların ümumi sayını müəyyənləşdirin. Nəticəni 1000000009 (10^9+9) modulu ilə verin.

Məhdudiyyətlər:

0 < N ≤ 10^6.

Giriş məlumatları:

Giriş faylının birinci sətirində — N ədədi.

Çıxış məlumatları:

Yeganə sətirdə — məsələnin cavabı.