**Problem Description**

If you think the answer is larger than 1e9+7, please output the answer mod 1e9+7.

**Input**

The first line contains a T which means the number of data sets.

In each data set:

one line contains one integers k.

T <= 128

k <= 128

**Output**

for each data set, output answer in one line.

**Sample Input**

2 1 10

**Sample Output**

2 59048

**Hint**

you can use every number within the given range as many times as you want but notice that only first discover of target can generate one happiness.

you can think (i,j) and (j,i) are different if and only if i != j.

**Source**

2018市赛