AlgoLiga 2018

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;10⁵]. Każdy test składa się z liczby naturalnej n ∈ [1;10⁹]. 

Wyjście

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

Przykład

Wejście:
3
1
2
3

Wyjście:
1
11
29

Ilustracja do 3 testu