Time Limit: 1000 ms

Memory Limit: 32768 ms


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.


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.


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


Sample Output




The First ACM-ICPC Nanjing Invitational Tourn