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 10⁹+7.

Constraints:
1 ≤ T ≤ 10³
1 ≤ N ≤ 10⁵