OHANISER  Ohani And The Series
Now a days, Ohani has become very expert in mathematics. Her teachers like her very much because of her excellent performance.
One day, one of her teacher gave her a problem to solve. He will give Ohani a number N. This will represent a table of N rows. The first row contains number from 1 to N. Then the next line will contain N1 numbers, In the second row, the first number will be the summation of the first two numbers (1 + 2) of the previous row, the second number will be the summation of the second two numbers (2 + 3) of the previous row and so on. Row 3 will have N2 numbers with same procedures. Same procedure follows for row 4, row 5, .... , row N. On the last row, there will be only a single number. Ohani has to tell that only number of the Nth row.
For example: If N = 4, then the table is:
1 2 3 4
3 5 7
8 12
20
So Ohani has to answer the last remaining number: 20.
She can answer when N is small, but can't when N is large. Can you help her?
Input
The first line contains the number of testcases T (T <= 100000).
Each of the test cases contain a number N where 1 <= N <= 100000.
Output
You have to output the case number and the required answer. As the number can be very large, output the answer modulo 1000000007.
Example
Input: 2
1
2 Output: Case 1: 1
Case 2: 3
hide comments
rishabh_1997:
20160707 06:48:48
Learnt modular exponentiation... Also good precomputation of formula 

vineetpratik:
20160704 14:40:58
make a formula>get tle>use modular exp>ac 

KD :
20160525 12:10:09
AC in one go :P


samanway1996:
20160509 18:34:32
Only precomputation is enough... no modular exponentiation is needed :P 

Anant Upadhyay:
20150803 10:31:43
Use modular exponentiation


Dhruv k14:
20150305 20:36:46
Not typing "Case n: " cost me 5 WAs aaaaaaargghhh


Roy Rohit:
20150210 19:19:06
what is the answer for 100000??? Last edit: 20150210 19:19:27 

Raj Kumar Chauhan:
20150201 16:04:04
TLE, WA, Overflow again and again :(


pk:
20150201 09:51:29
my 100 on spoj :)


Aman:
20150201 08:48:40
My 50th one .... :) 
Added by:  Raihat Zaman Neloy 
Date:  20141016 
Time limit:  0.5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 