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_18_03 - Flaga

W Bajtocji nadszedł dzień Święta Wojska Bajtockiego. Pan Bajteusz postanowił wywiesić przed domem flagę swej ojczyzny. Jest tylko jeden mały problem. Otóż Bajtocja nie posiada flagi jako takiej... Flagą Bajtocji nazwiemy dowolną flagę złożoną z pionowych pasków o kolorze czerwonym, zielonym lub niebieskim oraz czarnej obwódce, spełniającą podane warunki:

1. Dwa paski o tym samym kolorze nie mogą ze sobą sąsiadować.

2. Pasek w kolorze niebieskim musi znajdować się bezpośrednio pomiędzy paskami z których jeden ma kolor zielony, a drugi - czerwony (czyli niepoprawną flagą jest CZNZ).

Pan Bajteusz chciałby wiedzieć ile jest możliwych flag Bajtocji o podanej długości - w ten sposób będzie wiedział, czy uda mu się wywiesić je wszystkie.

 

Wejście

Wejście rozpoczyna liczba testów 1 ≤ t ≤ 500 000. Następnie każdy test w oddzielnej linii. Pojedynczy test składa się z jednej liczby całkowitej 1 ≤ n ≤ 106.

Wyjście

Dla każdego testu odpowiedź w oddzielnej linii - liczba możliwych flag Bajtocji składających się z n pasków modulo 1015.

Przykład

Wejście:
1
3

Wyjście: 4

Wyjaśnienie do przykładu:
Są 4 takie flagi: RGR, GBR, RBG, GRG

 


Dodane przez:Adam Bąk
Data dodania:2014-08-29
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.