## POWFIB - Fibo and non fibo

The problem is simple.

Find  (a^b) % MOD

where ,

a = Nth non-fibonacci number

b = (Nth fibonacci number)%MOD

MOD = 10^9+7

Consider fibonacci series as 1,1,2,3,....

Note : It is guaranteed that Nth non-fibonacci number will always be less than MOD value for every value of N used.

### Input

First line contains T , the number of test cases
Each next T lines contains a  number N.

First line contains T , the number of test cases.

Each next T lines contains a  number N.

### Output

Print T lines of output where each line corresponds to the required answer.

Announcement: Constraints are updated. Sorry for inconvenience occurred.

### Example

`Input:`
```3
3
2
1```
`Output:`
```49
6
4
```
`Explanation`
`For N=3 : 3rd non fibo number =7, 3rd fibo number=2. ans= (7^2) %MOD =49`
`For N=2 : 2nd non fibo number =6, 2nd fibo number=1. ans=(6^1) %MOD=6`
`For N=1 : 1st non fibo number =4, 1st fibo number=1.  ans= (4^1) %MOD =4`
`Constraints`
`1<=T<=100000`
`1<=N<=9*10^8`
`Note: Test cases have been updated and costraints are changed.  Those who get TLE or WA are suggested to resubmit. GOOD LUCK there.` [Lakshman]: 2015-07-19 12:47:40 @Mohib Your solution is no more faster, see the updated list. Best is .17s EDIT1:: now .06s Last edit: 2015-07-23 20:52:57 :.Mohib.:: 2015-07-19 08:19:31 @Lakshman awesome speed!! Congratulations...!! Last edit: 2015-07-19 20:50:18 [Lakshman]: 2015-07-18 18:01:09 @All problem is ready http://www.spoj.com/problems/POWFIB2/ Have fun :) Kata: 2015-07-18 15:01:19 @luckymastermin : I agree with you. And for the new problem I suggest that a, b <= 1e18. For more interesting, the value to calculate is (non_fib ^ fib) % mod, not (non_fib ^ (fib % mod)) % mod with mod is a prime <= 1e18 [Lakshman]: 2015-07-18 14:19:20 @wisfaq I mean with hard constraints we can get more elegant solution. I will prepare slightly different from this one. -reply-> cool. That will be great! Last edit: 2015-07-18 16:16:06 hrishabh: 2015-07-18 11:47:10 Finally!! Green :) wisfaq: 2015-07-17 21:44:16 @Lakshman: would that be that much harder then? Last edit: 2015-07-17 21:45:21 [Lakshman]: 2015-07-17 15:16:26 As this seems to easy we can create another version of this with higher constraints with n <=1e16 ~ 1e18 what other thinks. eightnoteight: 2015-07-16 19:48:59 nice one! and easy one as n <= 10**7 :?ToRpiDo: 2015-07-16 18:57:10 @ivar.raknahs : Can you plz check my submission, I think my algorithm is correct. :-( -reply-> your mod operation is incomplete. Good luck Last edit: 2015-07-18 16:30:28