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: ASM32-GCC ASM64 MAWK BC C-CLANG NCSHARP CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY3 R RACKET RUST SCM qobi CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Pochodzenie:ALGOLIGA

ukryj komentarze
2019-10-03 21:08:32 Sebastian Toton
@Adam Bąk

Może lekkie zmniejszenie limitu czasowego? Rozwiązanie w Javie nie za bardzo chce przejść :/
2014-10-03 22:36:01 Marcin Kasprowicz
W tym zadaniu należy użyć scanf i printf lub fast I/O
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.