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
Shashank Srivastava: 2015-12-13 09:18:28

Great problem, but very strict time limit. Had to optimize a lot.
@Francky can you give some hints for further optimization?
=(Francky)=> You have to find them for other problems, good luck.

Last edit: 2015-12-14 21:02:00
abdou_93: 2015-01-20 06:25:35

@Francky. why WA ! can you help me?
ID(13472432 last submission)
--Francky--> You should check again C2 and C3.
abdou-> thanks . nice problem

Last edit: 2015-01-20 16:31:04
mjh: 2014-12-24 07:44:55

how to handle 10^100 for input
--ans(Francky)--> You can store it in a string, or process it on the fly, char by char. But there's no numeric standard container for those numbers ; you have to handle that.
edit : I saw you used Python ; in that case you need a much better method.
thanks for reply. i first used python, but get tle. so i want to use c++, however i don't know how to handle the big input
--(Francky)--> In that case, the first answer suit.

Last edit: 2014-12-25 21:13:30
tyson: 2014-07-01 21:36:38

can someone help me on the time
i got AC in 2.9s and have no idea to improve it

Francis: 2014-04-28 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?
--ans(Francky)--> another key is to do smart precomputation. Please do not spoil on some part of the answer.

@Francky, hi Franky. Thx for your advice, you mean the scan part or ??? I know I need to improve my alg rather than using that part. I tried to use precomputation and I chose to precomputate Fib(n) with the big part of n in 0~MOD-1. However it seems that my precomputation only adds time rather than reduces time. I want to know how to deicde the range of n(the bigger n the better??? the larger n the better???) to be precomputated to reduce time efficiently, does that has something to do with the test cases??? I need your hints, Waiting for your reply! :)
--ans(Francky)--> precompute all take too much time, you have to do a smart precomputation method. I can't tell you more without spoiling. Good luck. Another tip : matrices are very slow, work only on some coeff, you will avoid redundant computations.

Last edit: 2014-04-28 14:11:48
pankaj bhardwaj: 2013-07-04 11:33:59

Is chinese not enough

[Lakshman]: 2013-05-12 06:33:59

Don't know how to handle 10^100...
--ans--> It's part of the problem.

Finally done!!!

Awesome problem !!!!!!!!!

Last edit: 2013-06-04 16:22:37
(Tjandra Satria Gunawan)(曾毅昆): 2013-01-22 05:28:46

After solve FIB64, FRSKT, and PISANO, this problem seems much easier... finally #1st place ;-)
--ans--> Good job and congratulations, there's still some small opti to be found ;-) a good ×2 is possible.

Last edit: 2013-01-22 07:13:20
Atul Vaibhav: 2012-10-25 14:28:51

Getting WA! what is the ans for 10^100 ??
--ans--> solve the problem and you'll know.
-- Hint : try to manage a brute force with python (for example) in order to debug. Good luck.

Last edit: 2012-10-25 20:56:45
(Tjandra Satria Gunawan)(曾毅昆): 2012-10-05 21:05:48

finally AC after silly mistake..
Why 0k mem usage??
--ans--> Some trouble on spoj servers, should be fixed in few times. (Warning, it slows submissions)
RE: I did my best (for now), I don't know other trick to speed up my code, maybe next time :-) Google +1 for this awesome problem..

Last edit: 2012-08-26 15:59:56

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