# Fibonacci Remixed

**Background**

HOBO got inspired by fibonacci series and decided to make his own series called HOBO series which has a recurrence relation

f(n)= 3*f(n-1)+ 2*f(n-2)+ 5.

You need to find the nth HOBO number following the above reccurence relation. As the answer can be large print it modulo 1000000007.

f(1)=0

f(2)=1

**Input**

1st line: An Integer T denoting the number of test cases.

Each test Case Contains: A single number n.

**Output**

You need to find the nth HOBO number modulo 1000000007 following the above reccurence relation.

**Sample Input**

```
```

3

1

2

10

**Sample Output**

```
```

0

1

66013

**Constraints**

Number of Test Cases T , 1 < T <= 1000

1 < n <= 10^9

*Problem Setter : Vivek Bhatnagar*

**Languages:**C,C++,Java