All Submissions


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

Time Limit: 2 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0