You will be given N. You have to find the expected value of building number with N bits.

More formally if you have 2 bits you can make (00)2 = (0)10 (01)2 = (1)10 (10)2 = (2)10 (11)2 = (3)10 but you have to find the expected value of building number with N bits in decimal number system. As the answer can be very big. You have to find the Mod value with 109 + 7.

Input

In the first line, there will be T denoting the number of test cases. In the next T lines, you will be given N denoting the number of bits.

Constraints:

1 <= T, N <= 100000

Output

Print the Mod value of the desired integer in the decimal number system with 109 + 7.

Sample

Input

Output

2
1
2

500000004
500000005

In probability theory, the expected value of a random variable is a key aspect of its probability distribution. Intuitively, a random variable's expected value represents the average of a large number of independent realizations of the random variable. For example, the expected value of rolling a six-sided die is 3.5, because the average of all the numbers that come up converges to 3.5 as the number of rolls approaches infinity. The expected value is also known as the expectation, mathematical expectation, mean, or first moment.