Ross is bored at the moment, so he decides to draw triangles. He starts by drawing an equilateral triangle on a piece of paper.Then he performs a set of moves. In the ith move he takes all the uncoloured triangles, divides each of them in 4 parts of equal areas and colour the central part. Also, he keeps on counting the total number of triangles after each move.

Initially :

After 1st move :

After 2nd move :

Given Q queries. For each query, given an integer N, and you have to count the total number of triangles after the Nth move. Since the answer can be very large output it modulo 10⁹ + 7.

Input

First line consists of an integer Q denoting the number of queries.
Each of the next Q lines consists of an integer N.

Output

Output Q lines, in each line denoting the answer for each query.

Constraints

1<=N,Q<=1000000