Rohit just started his 3rd semester classes in DMS. One of the interesting parts of DMS is set theory. He has just learnt about Power Set of any set, which is the number of ways in which you can create a unique subset from the existing set. Two subsets are said to be different if atleast one element in both the subsets are different.
Given the number of elements in the set, you need to print out the size of power set that can be obtained from the main set. Since the answer can be pretty huge, you need to print the answer modulo 10^9 + 7.

Input
The first line of the input contains an integer T denoting the number of test cases. Each of the T lines that follow have the number N denoting the number of elements in the main set.

Output
For each test case, print out the answer modulo 10^9 + 7.

Constraints

1 <= T <= 1000
0 <= N <= 10^15

Example
Input:
2
1
3

Output:
2
8

Explanation
Example case 2.
For N = 3, if main set is { 1, 2, 3 }, the subsets are : { }, { 1 }, { 2 }, { 3 }, { 1,2 }, { 1,3 }, { 2,3 }, { 1,2,3 }.

见题面

见题面