POWERPHI - Power of Phi(medium)

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 of these integers, 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 <= 100000

0 <= n <= 109

Example

INPUT:
2
1
3

OUTPUT:
2
4

Added by:darkshadows
Date:2013-03-28
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2020-09-05 06:51:01
Just consider the fact that phi^n is very close to an integer for large n. This is called a Pisot number. I personally dislike problems with fancy mathematical properties like this.
2016-07-08 12:45:47
any hints??
2015-03-04 18:02:50 Ankit
nice question,finally accepted:)
2015-02-05 21:36:59 Arya08


finally Green after 50(approx) wrong ans :)

Last edit: 2015-09-05 11:24:03
2014-12-25 19:40:04 Shaswat Chaubey
My 50th! Nice question, got many WAs on a ques for the first time. The soln. was nice too.
2014-12-20 15:48:56 [Lakshman]
@ISHANI I am not using ME, my algorithm is different it uses only 2 mod operation and 3 multiplication per test case. Hint->try to use 1.unsigned long long when ever possible reduce mod operation. 2 Fast I/O.

Last edit: 2014-12-20 15:49:22
2014-12-20 15:30:22 ISHANI
@lakshman my comlexity is also o(log n) per test case but my sol is accepted on 0.49 sec how your 0.09

Last edit: 2014-12-20 15:46:31
2014-09-07 22:08:00 [Lakshman]
@vikas what complexity of your algorithm
is? Here You need O(log n) per test.
2014-09-07 18:18:00 vikas
getting TLE using dp .. any suggestions ?
2013-12-05 19:36:25 Laxus!!
Please give some more bigger test cases!!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.