PHIPOWER  Power of Phi
Vertu was very impressed by the golden ratio φ = (1 + √5) / 2 and about it occurring in nature and all that. He now begins to wonder if any non negative integral power of φ is also special. Since he does not like working with decimals, he decided to approximate the positive integral power of φ to its closest integer. Help him by printing the closest integer to φ^{n}, given n.
Input
The first line contains t, the number of test cases. t lines follow, each containing one positive integer n.
Output
For each test case, print the closest integer to φ^{n}. If you think there are two closest possible integers, print either of them. Print the answer modulo(10^{9}+7).
Constraints
t <= 500
0 <= n <= 10^{6}
Example
Input: 2 1 3 Output: 2 4
hide comments
[Lakshman]:
20130501 13:05:55
@Lalit Kundu Can you Please check Don't know why getting WA with my java code.. Last edit: 20130501 15:05:57 

darkshadows:
20130328 13:27:32
Problem with harder constraints is at www.spoj.com/problems/POWERPHI Last edit: 20130328 13:26:40 

[Rampage] Blue.Mary:
20130328 13:27:32
PS: problem setter should set a new problem (and move this one to tutorial) instead of simply changing the constraints and rejudging. The constraints is a part of the problem. 

darkshadows:
20130328 13:27:32
PS: constraints have been updated and solutions rejudged. 
Added by:  darkshadows 
Date:  20130326 
Time limit:  1s 
Source limit:  5000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own problem 