In Dholakpur State, there are two cities city A and city B, there is a river between them.
King Indraverma wants to join both cities through a bridge. Work is going on of bridge . Jaggu is a civil engineer at this site.
Jaggu's team is building bridge. Bridge length is N and there are total 2N points both sides of baridge, each side of bridge has half the total number of points. His team have to set
poles at those points and there are two types of poles green and red. It is compulsary to set pole at each and every point. So, Jaggu has some condition to set poles:
1) No two red poles on the same side of bridge can be adjacent.
2) No two red poles on the different side of bridge can be exactly opposite to each other.
So Jaggu want to know how many number of ways his team can set poles to build bridge , so that Jaggu can complete his project and get some dozons of bananas as reward.

Note- There is no restriction on green poles
they are using green pole to controll traffic on the bridge because bridge has limited capacity of weight.

Input Format
First line has a positive input number as a test case T.
Following the t lines after the first line the length of bridge N is given.

Output Format
Output is an integer ,the total number of ways to build a bridge.
Take the output as the modulous of 1000000007.

Constraints
1 <= T <= 100
1 <= N <= 10^6