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
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?
The first line contains the number of testcases T (T <= 100000).
Each of the test cases contain a number N where 1 <= N <= 100000.
You have to output the case number and the required answer. As the number can be very large, output the answer modulo 1000000007.
2 Output: Case 1: 1
Case 2: 3
Learnt modular exponentiation... Also good precomputation of formula
make a formula->get tle->use modular exp->ac
AC in one go :P
Only precomputation is enough... no modular exponentiation is needed :-P
Use modular exponentiation
Not typing "Case n: " cost me 5 WAs aaaaaaargghhh
what is the answer for 100000???Last edit: 2015-02-10 19:19:27
Raj Kumar Chauhan:
TLE, WA, Overflow again and again :(
my 100 on spoj :)
My 50th one .... :)