Bob got a new contract of painting wall. Wall has N bricks. Bob can paint each brick with three type of colors : Type A, Type B and Type C. Assume Bob has enough amount of paints of all three types. Find number of ways Bob can paint the wall having N bricks with color of Type A, Type B and Type C such that no two adjacent brick should have same color.
Input:
First line of input contains number of test cases T. Each test case contains a single integer N, number of bricks in wall.
Output:
For each test case print the number of ways Bob can paint the wall. Answer can be too large print answer modulo 109+7.
Constraints:
1 ≤ T ≤ 103
1 ≤ N ≤ 105
Test Case #1:
Number of bricks in wall is 1. So Bob can paint that brick with color of Type A or Type B or Type C. Hence the answer is 3.
