FRS2  Fibonaccibonacci (easy)
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(N1) + FIB(N2)
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 (suboptimal) 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(1122017) 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
Shashank Srivastava:
20151213 09:18:28
Great problem, but very strict time limit. Had to optimize a lot.


abdou_93:
20150120 06:25:35
@Francky. why WA ! can you help me?


mjh:
20141224 07:44:55
how to handle 10^100 for input


tyson:
20140701 21:36:38
can someone help me on the time


Francis:
20140428 09:03:09
nice prob! actually it costs me a lot of time to get "key" and helps me review some basic knowledge of C~finally get 0.49s in C with fast I/O, and I have no idea how to improve my code, any suggestions?


pankaj bhardwaj:
20130704 11:33:59
Is chinese not enough 

[Lakshman]:
20130512 06:33:59
Don't know how to handle 10^100...


(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20130122 05:28:46
After solve FIB64, FRSKT, and PISANO, this problem seems much easier... finally #1st place ;)


Atul Vaibhav:
20121025 14:28:51
Getting WA! what is the ans for 10^100 ??


(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20121005 21:05:48
finally AC after silly mistake..

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