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.


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.


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

Announcement: Constraints are updated. Sorry for inconvenience occurred.


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
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
prbhatter: 2021-04-14 06:33:20

@nimphy is correct I think.... "b" should be calculated under modulo (MOD-1) and not MOD.
This link should explain why is it so -> https://www.geeksforgeeks.org/find-power-power-mod-prime/
If this is wrong, then please could someone explain why "b" should be computed under modulo MOD and not (MOD-1)?

[NG]: There is nothing one "should" do here other than what the problem statement stipulates.

Last edit: 2021-04-14 08:28:05
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!!

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

priyank: 2015-12-15 19:49:01

finally solved with lowest time in java after more than 25 tle and wrong answer :)

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