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
DIWAKAR BHARDWAJ:
20150801 13:12:23
easy one Ac in first attempt 

[Lakshman]:
20150801 07:05:13
@ivar.raknahs Why did you changed the constraints after 100 successful submission Please revert it back to the original. This is not a good practice. While rejudging did you check this option Refresh cached info about test sequence.


Arun:
20150726 17:18:11
amazing!! 

kp:
20150720 19:43:32
nice.. Last edit: 20150721 06:59:48 

[Lakshman]:
20150720 14:17:30
@Pulkit if you find this too easy you may give atry to this one.


Pulkit Singhal:
20150720 13:27:34
Easy One :)


:?ToRpiDo:
20150719 22:21:28
@ivar.raknahs & @[Lakshman] :: btw what should i do to make it faster Last edit: 20150719 22:23:25 

:?ToRpiDo:
20150719 21:59:02
After 10 WA's & TLE's.....finally green :)


Vaporeon:
20150719 17:05:40
2 days. finally AC ! :D :D 

harshit sharma:
20150719 13:34:54
giving w.a after 9 judge...

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 