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(0)=1 
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 :

Input:
2
3
5

Output:
4
32

hide comments
fitcat: 2012-04-01 17:22:33

From the definition of Fibonacci number, f(0) should be equal to 0.

numerix: 2012-04-01 17:22:33

@bashrc: Good decision. Thanks.

bashrc is back: 2012-04-01 17:22:33

@numerix: I see the point.And probably it must be clear to others from the comments that big integers may not pass.So i am opening for all languages.

numerix: 2012-04-01 17:22:33

@bashrc: That's what I supposed. So my questions:
1. Why, if bigint is the reason, is Java not excluded?
2. Why, if brute-force solutions obviously won't pass, is it not opened for all languages?

bashrc is back: 2012-04-01 17:22:33

@numerix I didn't wanted to distract newbie programmer's in using big number arithematic available in the languages i disallowed.In any case that solution won't pass.

numerix: 2012-04-01 17:22:33

Is there any reason for exclusion of some languages? If not, please open it for all languages.

! include(L.ppt): 2012-04-01 17:22:33

gud problem.....got ac with normal scanf.....:)

Reply:C and C++ programmers can take the liberty of using any I/O.The warning was for slower languages.

Last edit: 2012-03-24 17:21:35
Francky: 2012-04-01 17:22:33

with only 2000 test cases, there's no IO problems imaginable, imho.

Last edit: 2012-03-24 15:00:20

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