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(109+7).

Constraints

t <= 500

0 <= n <= 106

Example

Input:
2
1
3

Output:
2
4

Added by:darkshadows
Date:2013-03-26
Time limit:1s
Source limit:5000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem

hide comments
2013-05-01 13:05:55 [Lakshman]
@Lalit Kundu Can you Please check Don't know why getting WA with my java code..

Last edit: 2013-05-01 15:05:57
2013-03-28 13:27:32 darkshadows
Problem with harder constraints is at www.spoj.com/problems/POWERPHI

Last edit: 2013-03-28 13:26:40
2013-03-28 13:27:32 [Rampage] Blue.Mary
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.
2013-03-28 13:27:32 darkshadows
PS: constraints have been updated and solutions rejudged.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.