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
nimphy:
20180517 02:33:45
when I get “b”，I should mod 1e9+71，right？ But I get WA； while mod 1e9+7 get AC。What is the problem~~~~ 

darkdreamofmy1:
20170827 20:00:35
Wrong answer on test case 14 but why!! 

Shubham Jadhav:
20170506 04:23:08
Last edit: 20170506 04:39:46 

swjwy:
20170406 05:35:39
Last edit: 20170406 05:40:32 

sak3t:
20170102 15:06:28
I have got 3 WAs. I am sure my code is correct. :/


Ketan Chandak:
20160729 17:19:18
O(T*log(n)) gives TLE with scanf/printf. Too tight Time Limit? 

Sarthak Munshi:
20160605 09:21:23
@ivar.raknahs : can you please check my latest submission . Last edit: 20160605 16:53:07 

abhi_vicky:
20160225 08:31:07
using matrix exponantion....AC in one go. 

shubham:
20160114 13:25:05
Nice question!!!


anil2496:
20160111 19:11:47
learnt a lot 
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 