FRS2 - Fibonaccibonacci (easy)

no tags 

Leo would like to play with some really big numbers, OK...

Let FIB the Fibonacci function :
FIB(0)=0 ; FIB(1)=1
and
for N>=2 FIB(N) = FIB(N-1) + FIB(N-2)

Example : we have FIB(6)=8, and FIB(8)=21, so FIB(FIB(6))=21

Input

The input begins with the number T of test cases in a single line.
In each of the next T lines there are an integer N.

Output

For each test case, print FIB(FIB(N)) ,
as the answer could not fit in a 64bit container,
give your answer modulo 1000000007.

Example

Input:
3
0
5
6

Output:
0
5
21

Constraints

1 <= T <= 10^4
0 <= N <= 10^100

Time limit is set to allow (sub-optimal) 500B of python3 code to get AC.
A near optimal solution is within 0.02 and 0.04s with a fast language, and around 1s in Python2 without psyco.

Edit(20/I/2015) With Cube cluster, it is not hard to get 0.0s with fast languages, and my old code ended in 0.08s using PY3.4.

Edit(11-2-2017) With compiler update, new TL. My old Python code ends in 0.04s, and it's easy to get 0.00s using a fast language.


hide comments
Ehor Nechiporenko: 2012-10-05 21:05:48

Nice problem.
Needed before programming good mathematical precomputation.)))

And now I know solution for 10^100
--ans--> Congratulations. Indeed, precomp, or better : analysis, ... for FRSK* it will be necessary.

Last edit: 2012-08-23 16:01:21
tille: 2012-10-05 21:05:48

haha ....
1 google of input, 10^100...
Good problem :)

Last edit: 2012-08-22 04:26:47
:D: 2012-10-05 21:05:48

Don't know how to solve it yet, but still has to say a very well made problem. Finally some interesting twist on Fibonacci tasks.

Most of all, it's great that you did a detailed time analysis. Really saves the users a lot of trouble!
--ans--> To do it in Python will not be easy, here's the real challenge. This problem is mostly to make in appetite for FRSKH ...
Thanks for your appreciation.

Last edit: 2012-08-22 18:52:08

Added by:Francky
Date:2012-08-19
Time limit:0.300s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem