We have all heard about the story in which Emperor Akbar sentences his court dancer Anarkali to be buried alive behind a wall. Actually his son Salim fell in love with the dancer, and Akbar did not want to marry his son to a lower class dancer. So he ordered his men to build a 2D wall infront of Anarkali.

Now there are three kind of bricks in Akbar's kingdom. Red colored brick of size 1x3, Green colored brick of size 1x2 and blue colored brick of size 1x1. Akbar wants to know the number of ways his men can build the wall of size Nx3, N being the height of Anarkali and 3 is her width, using the types of brick mentioned. Note that the bricks can be used horizontally as well as vertically. So the red and green bricks can be used in two different ways (horizontally and vertically) while the blue brick can be used only in one way (being of size 1x1, it is immaterial how you place the brick).

As usual Akbar calls Birbal to find the answer for him. You being the computer programmer of Birbal is supposed to do the work for him. Note that two wall are considered different if their front view appears of different color at any point.

Input & Output:
The first line of the input contains the number of test cases T. Next T lines contains an integer each N, the height of Anarkali.For each input N, output the number of ways to build the wall. As the answer can be huge print the answer modulo 10^9 + 7.

Constraints:
T ≤ 100
1 ≤ N ≤ 10^6SAMPLE INPUT
2
1
2

SAMPLE OUTPUT
4
29

Explanation

For sample case 2, refer to the image above.

见题面

见题面