POWFIB  Fibo and non fibo
The problem is simple.
Find (a^b) % MOD
where ,
a = Nth nonfibonacci number
b = (Nth fibonacci number)%MOD
MOD = 10^9+7
Consider fibonacci series as 1,1,2,3,....
Note : It is guaranteed that Nth nonfibonacci 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.
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.
hide comments
priyank:
20151215 19:49:01
finally solved with lowest time in java after more than 25 tle and wrong answer :) 

mukesh227:
20151030 19:33:55
after 4 WA finally AC!!!!!


surya97:
20151027 08:00:59
hurray! got accepted. :)


surya97:
20151026 19:38:32
@author: please help why i am getting wrong answer after case 15. many WAs.


surya97:
20151026 14:29:29
i am getting WA after 12th test case @ivar.raknahs Last edit: 20151026 14:33:19 

Aditya Kumar:
20151023 08:33:16
Wrong Data Type costed me couple of WA!!


tinneminy:
20150822 12:22:24
@ivar.raknahs : Can you plz check my submission ID14951756. I already got more than 8 WA. Don't know where i m wrong. 

weathervane:
20150821 21:20:56
@ivar.raknahs I'm confused. The time limit is 1 second, but today answers taking 3 seconds were accepted.


Dune:
20150817 13:28:58
@ivar.raknahs : testcases have been updated with cases where N>10^7, but previous submissions haven't been rejudged, you'll have to rejudge it.


kartikay singh:
20150805 14:21:26
@ivar.raknahs : Can you plz check my submission I think my algo is correct :(

Added by:  ivar.raknahs 
Date:  20150715 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 JSMONKEY 
Resource:  OWN 