CODERE4 - Coder Express 4!!

no tags 

Coder Express Le!!

Thangabali won the contest and Meenamma was not ready to marry him so she ran away with Rahul to a town where Thangabali was trained. The experts helped Rahul in solving the toughest question and help improve his coding skills. As a final challenges:They ask him solutions to some sequences.

The first sequence was : 0 1 1 2 3 5 8 13.....
Rahul easily fugured out and answered it is fibonacci F(n)=F(n-1)+F(n-2) n>=2,and F[n]=1 for n=0,1

The second sequence which they gave were: 1 1 3 7 17...
After thinking for a while Rahul answered it as F(n)=2*F[n-1]+ F[n-2] n>=2,and F[n]=1 for n=0,1

They were very impressed and they asked him to build the solution for the third sequence and then he is well trained to defeat anybody?
The third sequence was 1 1 3 8 20 50 123...and so on

Rahul was unable to figure it out .Your task is to tell him the nth term of the third sequence so that he could easily solve the problem.


Input Specification:

First line contains an integer T(1 < = T< = 1000) that represents the number of test cases.Then follows the T containg the integer N(1< = N< = 1000000000) specifying the term to be printed.

Output Specification:

For each test case, print only one line, the nth term
Since the output would be very large you have to print your answer modulo 1000000007.

Sample input:


Sample Output:


hide comments
ansisg: 2018-09-08 19:38:04

robert, its not that thing. there is number 126, but here - 123. but it's still almost impossible.

Himanshu Srivastava: 2013-09-21 19:07:43

nice hint-- figure out the reason why the above two series are mentioned :D

Andy: 2013-09-05 08:44:43

answer for n=1000 please?

Robert Gerbicz: 2013-09-02 22:38:42

To sum up: if the order is 3, then there is a problem with the output file (yes, non integer terms, but the problem is still good), and in that case I would say it is a classical problem. For higher order it is a riddle problem, you say nothing about the sequence, we see only (few) integer terms.

Mitch Schwartz: 2013-09-02 22:38:42

FYI, I saw this in classical about an hour ago and moved it to riddle, I guess at about the same time @Robert Gerbicz submitted. All I noticed before moving to riddle is that f(n)=(8*f(n-1) - 2*f(n-2) + 2*f(n-3))/3 for n>3 works, but gives non-integer values (although they will be integers mod 10^9+7).

Last edit: 2013-09-01 23:00:51
Robert Gerbicz: 2013-09-02 22:38:42

Was it a competiton problem? If it is then this problem is really broken and we see too few terms to find it (without Neil Sloane). If the order of the sequence is 3 then the problem is also broken (tried it).

Last edit: 2013-09-01 23:23:21

Added by:Rajesh Kumar
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:AASF - ABV-IIITM PC-01-9-2013