Emperor of Algops wanted a giant wall around his kingdom to protect the empire from various nomadic groups. The best architect Nirmata was appointed for the task.

In order to minimize the cost of raw material, Nirmata is restricted to use only following three kinds of building blocks::

X     # 
XX 

The length of the wall is fixed and is 2 units, but the height of the wall varies. As a part of his job Nirmata needs to find out the number of ways he can construct the wall using above two types of building blocks where the height of the wall is specified. Write a program to help Nirmata.

Input
The first line contains the number of test cases T followed by T lines. Each of the next lines contains an integer N representing the height of the wall.

Output
Print T lines one for each test case, containing an integer that represents the number of ways of constructing the wall, modulo 1000000007

Constraints 1≤T≤1000 , 1≤N≤10^9