You are given a recursive formula to generate elements of the array First element of the array is "1" Second element of the array is "6"
Array[]=((Array[i-1]+ 2) 2 Array[i-21) for (>2 You need to print the Nth element of the array
Input format
The input starts with T. the number of Test Cases. Next T lines contain integer N.
Output format For each test ce print the answer on a single line. As the answer can be very large, output it modulo 10 9+7
Constraints 1<= T <=10^5 1
Sample Input 223
Sample Output 6 15
Explanation For the second test case: Array[3] =( (Array[2]+ 2)2-Array[1])=(6+2)2-1-15