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
Francis:
2014-04-15 11:13:34
I know there must be a simple formula for this kind of probs~
|
|
Bharath Reddy:
2012-07-18 11:29:55
Brute force to pre-compute fibonacci numbers works easily
|
|
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!!!
|
|
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!"
|
|
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 |
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 |