Ashwin is trapped in a B12 Hostel but in a parallel universe. The room numbers in this Hostel are different from usual, they consist of only 3 digits 5,6 and 7. Ashwin is given the maximum number of digits in a room number n, i.e. number of digits in a Room number will be from 1 to n. And to get out of this hostel Ashwin has to tell the maximum number of rooms possible in the Hostel (Room numbers are unique)
Since the answer can be large take modulus with 1000000007.
Input
The first line contains a single integer t (1≤ t ≤5) -- the number of test cases.
The next t lines contain a single integer n(1≤ n ≤30) i.e. maximum length of room number
Output
For each test case print a single line containing the maximum number of rooms in the B12 of Parallel Universe.
for n=1, room numbers will be 5, 6, 7 so the maximum number of rooms will be 3.
for n=2, room numbers will be 5, 6, 7, 55, 56, 57, 65, 66, 67, 75, 76, 77 so maximum number of rooms are 12.
