OPC3A - Arya and the exponacci

no tags 

Arya is very fond of fibonacci numbers.He claimed he can solve any problem on fibonacci number.His clever friend golu gave him a challenge 

to prove his skills.He gave him a sequence which he called exponacci.The sequence is given by 
g(n)=2^f(n-1) for n>0 
g(0)=1 for n==0 
f(n) denotes the nth fibonacci number where 
f(1)=1 (Obviously golu is not as good as arya in fibonacci numbers so he believes f(0)=1,anyways we have chosen not to disturb him)
f(n)=f(n-1)+f(n-2) for n>1 
Help arya to find the nth exponacci number.Since the numbers can be very large take mod 10^9+7

Input : 
The first line of the input will be the number of test cases(T<=2000). For each test case first line contains one integers n 0 <= n <= 1000000

Output :
The value of g(n)%(10^9+7)

Sample Cases :



hide comments
Francis: 2014-04-15 11:13:34

I know there must be a simple formula for this kind of probs~

PS:I failed using matrix exponentiation without MOD and fib(1000000) is overflow.

Last edit: 2014-04-15 11:20:12
Bharath Reddy: 2012-07-18 11:29:55

Brute force to pre-compute fibonacci numbers works easily

RE:The trick lies not in calculating the fibonacci in an eficient way. Its about understanding the maths behind the problem. You made the mistake in your first attempt. Hope you learnt from that

Last edit: 2012-07-20 12:25:51
devu: 2012-07-12 07:42:26

source code limit is destroying the beauty of the question !! plz increase it...

pushap: 2012-07-05 06:33:48

Any better approach than Brute force!!!
have tried by companion matrix but doesn't succeed

Sandeep Singh Jakhar: 2012-05-15 18:00:51

Time limit too high..

Sachin Railhan: 2012-05-01 20:46:02

I cant submit solution to this problem.When i try to, judge says "Your solution is too long for this problem, the limit is 1000 bytes!"

REPLY: Try to reduce the length of your code.1000 bytes is more than sufficient for this problem.

Last edit: 2012-05-03 13:59:07
Ehor Nechiporenko: 2012-05-01 10:27:56

What a nice problem

Devil D: 2012-04-13 13:41:53

Simple Brute force worked for me ..

bashrc is back: 2012-04-02 17:24:43

@leppyR64 it was modified after fitcat's comment.Thanx fitcat for pointing that out.

LeppyR64: 2012-04-01 21:54:38

@fitcat: that's why the comment in the problem statement.

Added by:bashrc is back
Time limit:1s
Source limit:1000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Resource:Own problem used in MNNIT LOCAL OPC