Count Ways to Complete Journey in Triangular Pyramid

Given a triangular pyramid with vertices marked as ‘O’, ‘X’, ‘Y’, and ‘Z’, and an integer 'N', you need to calculate the number of ways Bob can start at ‘O’, take exactly 'N' steps, and return to ‘O’. Each step allows movement to any adjacent vertex.

You must return the result modulo 1000000007 as the output can be very large.

Input:

The input contains multiple test cases. Each test case provides:

• An integer ‘T’ denoting the number of test cases.
• For each test case, an integer ‘N’ indicating the number of steps.

Output:

For each test case, output the number of ways as a single integer, each on a new line for each test case.

Example:

Input:

T = 3
N = 1
N = 2
N = 3

Output:

0
3
6

Explanation:

- For ‘N’=1, there are 0 ways to return to ‘O’ in one step.
- For ‘N’=2, valid sequences: O->X->O, O->Y->O, O->Z->O, totaling 3 ways.
- For ‘N’=3, valid sequences: O->X->Y->O, O->X->Z->O, O->Y->X->O, O->Y->Z->O, O->Z->X->O, O->Z->Y->O, totaling 6 ways.

Constraints:

• 1 <= T <= 100
• 1 <= N <= 10000