Thomson is very weak in set theory. Recently, he came across the following problem:
Given a set X with N distinct elements, in how many ways can you select two sets A and B such that both A and B are subsets of X and A is also a subset of B.
Help Thomson solve the above problem. As the answer can be very large, print it modulo 10^9+7.

Input:

The first line will contain an integer T denoting the number of testcases.
Each test case will contain only 1 line containing the cardinality (i.e. number of elements) of the set.

Output:

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

Constraints:
1 ≤ T ≤ 10^5
0 ≤ N ≤ 10^9

SAMPLE INPUT
2
9
50

SAMPLE OUTPUT
19683
710104287
noOfTestCases = int(raw_input())

div = pow(10,9) + 7

for caseNo in range(1, noOfTestCases + 1):
	elmentCount = int(raw_input())
	print pow(3,elmentCount, div)