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_21_09 - Puzzle

Masz dany prostokąt o wymiarach 3×n. Na ile różnych sposobów można wypełnić ten prostokąt prostokątami o wymiarach 2×1 tak, aby żadne pole nie pozostało puste? Wynik przedstaw modulo 109+7.

Przykładowe ułożenie prostokątów

Wejście

W pierwszym wierszu liczba testów t ∈ [1;10].

Każdy test składa się z jednej liczby naturalnej n ∈ [1;109].

Wyjście

Dla każdego testu należy w osobnej linii wypisać liczbę możliwych ułożeń modulo 109+7.

Przykład

Wejście:

3
1
2
4

Wyjście:

0
3
11

Dodane przez:Bartek
Data dodania:2015-03-06
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 JS-MONKEY
Pochodzenie:ALGOLIGA
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.