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_22_03 - Bezpieczne konie

Filip rozmyśla o szachach cały czas, rozmawia wyłącznie o nich, a nawet o nich śni. Codziennie wymyśla kolejne problemy związane z szachami i po rozwiązaniu każdego z nich nagradza się jednym Knoppersem. Podczas spożywania kolejnego triumfalnego batona, Filip zauważyl pana prowadzącego konia, na którym siedziała rozweselona dziewczynka, podziwiająca widoki z niecodziennej dla niej wysokości. Naszemu amatorowi szachów od razu naszło skojarzenie z jedną z figur szachowych - skoczkiem (nazywany również koniem). Filip uznał to za przeznaczenie i postanowił, że kolejny problem będzie dotyczył właśnie tej figury.

Doświadczony gracz długo nie musiał myśleć. By posmakować kolejnego batona musi stwierdzić na ile sposobów można postawić na szachownicy o wymiarach 2 x n co najmniej 2 skoczki by żaden nie zabił innego. Jako że Filip jest schizofrenikiem, a Ty jesteś jedną z jego osobowości, dostarcz do swojego ciała endorfin spożywając Knoppersa po napisaniu programu, który odpowie na postawione przez Ciebie pytanie.

Wejście

Pierwsza linia wejścia zawiera liczbę testów t ∈ [1;105]. Każdy test składa się z liczby naturalnej n ∈ [1;109]. 

Wyjście

Dla każdego testu odpowiedź na Twoje pytanie modulo 109+7.

Przykład

Wejście:
3
1
2
3 Wyjście: 1
11
29

Ilustracja do 3 testu

Możliwe rozstawienia koni na szachownicy o wymiarze 2x3


Dodane przez:Piotr Kąkol
Data dodania:2015-04-25
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: GOSU
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.