Triple

Time Limit: 1000 ms

Memory Limit: 32768 ms

Description

Once upon a time there is an ancient kingdom, The emperor of the kingdom has a so strong mind to manage his land that he divide the kongdom to n(0<n<10^9) states! And he likes to go on a tour of inspection very much. He plans to travel everyday, and for each tour, he chooses a different combination of states to visit.

People in this kingdom, strangely enough, use the ternary system to count numbers, and the emperor prefer 1 to be the last digit of a number. So the number of states he choose would only be 3k+1 while k is an integer. Then, he would like to know how many combinations he can choose from to travel. As is known to all, emperors should study more of policy than maths and programming. So he turns to you, the most excellent mathematician and programmer, to give him the answer.

Input

First line contain an integer t(t<=100), which means t cases follow. Then comes t lines, each contains an integer n, which means the emperor has divided the kingdom to n states.

Output

For each case, output one line showing the number of combinations according to the emperor's request. As the answer may be very large, you should print it after module 1000000007(i.e. 10^9+7).

Sample Input

2
1
5

Sample Output

1
10

Hint

Source

The First ACM-ICPC Nanjing Invitational Tourn

提交代码