AlgoLiga 2018

Jasiu i Stasiu postanowili zagrać w klasy, szybko jednak znudziła im się klasyczna gra, bo nie miała w sobie żadnej strategii. Postanowili zmienić zasady i z gry ruchowo-zręcznościowej uczynić ją grą umysłową. Zasady są proste, Jasiu podaje numer pola, a Stasiu musi odpowiedzieć, na ile sposobów może on dostać się z pierwszego na podane pole, jeśli może przeskakiwać o jedno, dwa lub trzy pola do przodu. Ponieważ liczba sposobów może być liczbą większą niż największa liczba jaką zna Jasiu, Stasiu musi podać ją modulo 1000000009.

Wejście
W pierwszym wierszu wejścia znajduje się liczba przypadków testowych d (1 ≤ d ≤ 10⁴). Każdy przypadek to jedna liczba całkowita n (2 ≤ n ≤ 10⁶) oznaczająca n-te pole, o które zapytuje Jasiu.

Wyjście
Dla każdego przypadku testowego należy podać liczbę sposobów dostania się z pierwszego na n-te pole, modulo 1000000009.

Przykład

Wejście
2
4
6

Wyjście
4
13

Z pierwszego na czwarte pole Jasiu może dostać się na cztery sposoby: (1,1,1), (1,2), (2,1), (3).