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
hide comments
Varun Kumar:
2013-03-29 20:29:58
@Kevin-not necessary. |
|
Kevin Sebastian:
2013-03-29 17:16:51
is precomputing necessary? |
Added by: | darkshadows |
Date: | 2013-03-28 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |