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 N-1 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 N-2 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

Added by:Raihat Zaman Neloy
Date:2014-10-16
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2015-01-23 14:27:50 VISHAL DEEPAK AWATHARE
what is the formula you are talking about?
2015-01-18 11:07:51 KK
My 50th
2015-01-15 19:31:42 Diksha Jaiswal
modular exponentiation is the key!! AC :)
2014-12-29 11:57:19 ROHIT RAJ
learned something new :)
2014-12-28 19:44:22 Anand
make a formula -> submit -> if TLE -> then wiki modular exponentiation = AC :)
2014-12-26 09:38:54 Abhishek
TLE in python after using formula , Help
2014-12-06 06:08:29 [Lakshman]
@ Ravi Teja It is possible with Java with direct formula as well with pre-computation. If you are using direct formula you need fast I/O like BufferedReader inout and output. Try not to use System.out.print it is too slow.
Hope this help.

EDIT1:: My best with Java fast I/O .10s.

Last edit: 2014-12-06 06:09:59
2014-12-05 20:20:52 Ravi Teja
Don't you think the time limit is too strict for Java? Getting TLE even for straightforward formula application
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.