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(n1) 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(n1)+f(n2) 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:
20140415 11:13:34
I know there must be a simple formula for this kind of probs~


Bharath Reddy:
20120718 11:29:55
Brute force to precompute fibonacci numbers works easily


devu:
20120712 07:42:26
source code limit is destroying the beauty of the question !! plz increase it...


pushap:
20120705 06:33:48
Any better approach than Brute force!!!


Sandeep Singh Jakhar:
20120515 18:00:51
Time limit too high.. 

Sachin Railhan:
20120501 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:
20120501 10:27:56
What a nice problem 

Devil D:
20120413 13:41:53
Simple Brute force worked for me .. 

bashrc is back:
20120402 17:24:43
@leppyR64 it was modified after fitcat's comment.Thanx fitcat for pointing that out. 

LeppyR64:
20120401 21:54:38
@fitcat: that's why the comment in the problem statement. 
Added by:  bashrc is back 
Date:  20120324 
Time limit:  1s 
Source limit:  1000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Own problem used in MNNIT LOCAL OPC 