Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_20_05 - Gra w klasy

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 ≤ 104). Każdy przypadek to jedna liczba całkowita n (2 ≤ n ≤ 106) 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).


Dodane przez:Mariusz Śliwiński
Data dodania:2014-12-17
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
Pochodzenie:ALGOLIGA
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.