OPC3A - Arya and the exponacci
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:
|
|
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.....:)
|
|
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 |