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.