Let there be given n points: P₁, P₂ ... P_n arranged in this order on a line. We would like to color them using four colors: white, black, red, and blue, in such a way that for every three consecutive points it is true that either:

• 1. the colors of these three points are pairwise distinct, or
• 2. the color of some point is white.

Input

An integer T, denoting the number of testcases (T < 100000). In each line you are given one positive integer (n < 1000000000). There are 5 input sets.

Output

Find the number of possible colorings of the n points. Since the answer can be very big, output only the answer modulo 1000000007.

Example

Input:
4
1
2
3
1000

Output:
4
16
43
283570349

Warning: large input/output data, be careful with certain languages

Warning: A naive algorithm will probably solve only the first input set.