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.
1st line: An Integer T denoting the number of test cases.
Each test Case Contains: A single number n.
You need to find the nth HOBO number modulo 1000000007 following the above reccurence relation.
Number of Test Cases T , 1 < T <= 1000
1 < n <= 10^9
Problem Setter : Vivek Bhatnagar