Santosh and yoga
Santosh does yoga every morning and that is the secret behind his concentration level. But one fine day his friend Kishore gave him a problem to solve. He gave Santosh a number N. This represented a table of N rows. The first row contains number from 1 to N. Then the next line contains N-1 numbers. In the second row, the first number is the summation of the first two numbers of the previous row, the second number is the summation of the second two numbers of the previous row and so on. Row 3 is having N-2 numbers with same procedures. Same procedure follows for row 4, row 5, ... , row N. On the last row, there is only a single number. Santosh has to tell the number in the Nth row.
For example: If N = 3, then the table is:
1 2 3
So Santosh has to answer the last remaining number 8.
He is very comfortable answering the problem when N is small but faces difficulty when N becomes large. Can you help him?
The first line contains the number of testcases T.
Each of the test cases contain a number N .
You have to output the case number and the required answer. As the number can be very large, output the answer modulo 1000000007.
Input: 2 1 2 Output: Case 1: 1 Case 2: 3
|Tags||giriraj, modulo, progression|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.