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.

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

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 constraints are changed. Those who get TLE or WA are suggested to resubmit. GOOD LUCK there.


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

hide comments
2022-12-06 14:07:56
<snip>
[Simes]: read the footer, don't post code here

Last edit: 2022-12-06 17:09:38
2022-12-06 12:20:51

How to find a number that is not Fibonacci?
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
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~~~~
2017-08-27 20:00:35
Wrong answer on test case 14 but why!!
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
2016-07-29 17:19:18 Ketan Chandak
O(T*log(n)) gives TLE with scanf/printf. Too tight Time Limit?
2016-06-05 09:21:23 Sarthak Munshi
@ivar.raknahs : can you please check my latest submission .

Last edit: 2016-06-05 16:53:07
2016-02-25 08:31:07
using matrix exponantion....AC in one go.
2016-01-14 13:25:05 shubham
Nice question!!!
constraints are good.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.