SP14330 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**.

The first line contains **T**, the number of test cases. **T** lines follow, each containing one positive integer **n**.

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 (10 $ ^{9} $ +7).