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.

hide comments
nimphy: 2018-05-17 02:33:45

when I get “b”,I should mod 1e9+7-1,right? But I get WA; while mod 1e9+7 get AC。What is the problem~~~~

darkdreamofmy1: 2017-08-27 20:00:35

Wrong answer on test case 14 but why!!

Shubham Jadhav: 2017-05-06 04:23:08

Last edit: 2017-05-06 04:39:46
swjwy: 2017-04-06 05:35:39

Last edit: 2017-04-06 05:40:32
sak3t: 2017-01-02 15:06:28

I have got 3 WAs. I am sure my code is correct. :/
WA on 14th test. Everytime. -_-

EDIT: Got it. Stupid mistake -_-

Anyways I have got AC in 6.06 s. Is there any better approach, I used matrix exponentiation?

Last edit: 2017-01-08 20:47:53
Ketan Chandak: 2016-07-29 17:19:18

O(T*log(n)) gives TLE with scanf/printf. Too tight Time Limit?

Sarthak Munshi: 2016-06-05 09:21:23

@ivar.raknahs : can you please check my latest submission .

Last edit: 2016-06-05 16:53:07
abhi_vicky: 2016-02-25 08:31:07

using matrix exponantion....AC in one go.

shubham: 2016-01-14 13:25:05

Nice question!!!
constraints are good.

anil2496: 2016-01-11 19:11:47

learnt a lot


Added by:ivar.raknahs
Date:2015-07-15
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY
Resource:OWN