Valid Flower Arrangements

You are given a number of flowers N and you need to determine the number of valid arrangements for planting these flowers. The number of arrangements is defined by the recurrence:

\( f(1)=3 \), \( f(2)=6 \) and for \( n \ge 3 \),

\( f(n)=f(n-1)+2\,f(n-2) \) modulo \( 10^9+7 \).

Your task is to compute \( f(n) \) for each test case.

inputFormat

The input is read from standard input (stdin). The first line contains an integer \( T \) representing the number of test cases. Each of the following \( T \) lines contains a single integer \( N \) which denotes the number of flowers.

outputFormat

For each test case, output the number of valid flower arrangements on a new line to standard output (stdout), computed modulo \( 10^9+7 \).

## sample

1
1

3

</p>