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
2015-07-19 13:34:54 harshit sharma
giving w.a after 9 judge...
any tricky case
2015-07-19 12:47:40 [Lakshman]
@Mohib Your solution is no more faster, see the updated list. Best is .17s

EDIT1:: now .06s

Last edit: 2015-07-23 20:52:57
2015-07-19 08:19:31 :.Mohib.:
@Lakshman awesome speed!! Congratulations...!!

Last edit: 2015-07-19 20:50:18
2015-07-18 18:01:09 [Lakshman]
@All problem is ready http://www.spoj.com/problems/POWFIB2/
Have fun :)
2015-07-18 15:01:19 Kata
@luckymastermin :
I agree with you. And for the new problem I suggest that a, b <= 1e18. For more interesting, the value to calculate is (non_fib ^ fib) % mod, not (non_fib ^ (fib % mod)) % mod with mod is a prime <= 1e18
2015-07-18 14:19:20 [Lakshman]
@wisfaq I mean with hard constraints we can get more elegant solution.

I will prepare slightly different from this one.
-reply-> cool. That will be great!

Last edit: 2015-07-18 16:16:06
2015-07-18 11:47:10 hrishabh
Finally!!
Green :)
2015-07-17 21:44:16 wisfaq
@Lakshman:
would that be that much harder then?

Last edit: 2015-07-17 21:45:21
2015-07-17 15:16:26 [Lakshman]
As this seems to easy we can create another version of this with higher constraints with n <=1e16 ~ 1e18 what other thinks.
2015-07-16 19:48:59 eightnoteight
nice one!
and easy one as n <= 10**7
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.