CODERE4  Coder Express 4!!
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(n1)+F(n2) 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[n1]+ F[n2] 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:
3
1
2
3
Sample Output:
1
1
3
hide comments
ansisg:
20180908 19:38:04
robert, its not that oeis.org thing. there is number 126, but here  123. but it's still almost impossible. 

Himanshu Srivastava:
20130921 19:07:43
nice hint figure out the reason why the above two series are mentioned :D 

Andy:
20130905 08:44:43
answer for n=1000 please? 

Robert Gerbicz:
20130902 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:
20130902 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(n1)  2*f(n2) + 2*f(n3))/3 for n>3 works, but gives noninteger values (although they will be integers mod 10^9+7). Last edit: 20130901 23:00:51 

Robert Gerbicz:
20130902 22:38:42
Was it a competiton problem? If it is http://oeis.org/A187003 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: 20130901 23:23:21 
Added by:  Rajesh Kumar 
Date:  20130901 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  AASF  ABVIIITM PC0192013 