Roy bought a Ring for Alfi, his girlfriend :p. But Alfi will only accept the Ring if Roy played a game with her and answered her queries correctly during the game.

Alfi places a ring at origin of a Cartesian Plane. Both Alfi and Roy move the ring alternatively. Alfi takes odd steps and Roy takes even steps.

Direction of Movement: Alfi always moves either left or right alternatively, i.e. if she moved left in her last step, she will move right in her current step. Initially she moves right. Roy always moves up or down alternatively, i.e if he moved up in his last step, he will move down in his current step. Initially he moves up.

Displacement of Ring: Initially both of them displace the ring by 1 unit. During Alfi's turn(other than her first step), she sums up her last displacement and Roy's last displacement, and moves the Ring by the value thus obtained. Similary, during Roy's turn(other than his first step), he sums up his last displacement and Alfi's last displacement, and moves the Ring by the value thus obtained.

Sample example of movements:

Now that the direction and displacement of Ring's movements are clear. Its time to answer Alfi's weird queries.

Given the step number N, what is the perpendicular distance of Ring from Y-axis after that step. Now Alfi is such an impatient girl, she wants him to answer as quickly as possible, otherwise she won't accept the Ring.

Input:

First line of input will contain integer Q, number of queries. Next Q lines each will contain integer N, step number of the game.

Output:

Print the result of each query in a new line. Since the result can be very large, print it modulo 1000000007

Constraints:

1<=Q<=10000

1<=N<=1000000000