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
Soma: 2015-07-15 19:20:03

@anyone : is a>0 or a>=0 ?

--(ans)-- a>0

Last edit: 2015-07-15 19:20:46
Kata: 2015-07-15 18:49:15

@luckymastermin :
This problem ask to calculate (non_fib ^ (fib % mod)) % mod, not (non_fib ^ fib) % mod

[Lakshman]: 2015-07-15 18:27:36

@ivar.raknahs I think the entire INPUT file is wrong you check my code AC one and wrong answer.

NOTE:: how come you are calculating non Fibonacci ^ Fibonacci on same mod which is 1000000007.

here we need to apply Euler's theorem in order to solve this. But as I checked your input file based on mod 1000000007 only.

-reply-> you need to calculate (a^ (b % mod ) ) % mod not (a^b)%mod and please read the note statement. I hope this helps.

Last edit: 2015-07-16 05:23:57
Abhishek Guha: 2015-07-15 18:05:00

I am getting WA :(
@mohib, can you check my code ?

:.Mohib.:: 2015-07-15 17:47:10

Assuming n<=10^7 and t<=10^5. I got AC :)

[Lakshman]: 2015-07-15 17:33:10

Please mention the upper and lower bound for n. Can you check my submission, I think my algorithm is correct.

:.Mohib.:: 2015-07-15 14:07:47

What is the bounds for n and t??
-reply-> constraints updated

Last edit: 2015-07-16 05:04:49

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