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-08-05 14:21:26 kartikay singh
@ivar.raknahs : Can you plz check my submission I think my algo is correct :(
2015-08-01 13:12:23 DIWAKAR BHARDWAJ
easy one Ac in first attempt
2015-08-01 07:05:13 [Lakshman]
@ivar.raknahs Why did you changed the constraints after 100 successful submission Please revert it back to the original. This is not a good practice. While re-judging did you check this option Refresh cached info about test sequence.

reply->"Refresh cached info about test sequence." what is this for? Can you elaborate?

==(Lakshman)=>It clears the last saves running time from cache and update with new running time. Eg if the running time before Re-judge is 1.2s and after re-judge is 1.4s it will update with the new running time not with the last one.

Last edit: 2015-08-02 06:22:09
2015-07-26 17:18:11 Arun
amazing!!
2015-07-20 19:43:32 kp
nice..

Last edit: 2015-07-21 06:59:48
2015-07-20 14:17:30 [Lakshman]
@Pulkit if you find this too easy you may give atry to this one.
http://www.spoj.com/SPOJ/problems/POWFIB2/

Last edit: 2015-07-20 14:32:47
2015-07-20 13:27:34 Pulkit Singhal
Easy One :)
@Laxman Solved the POWFIB2, But my time is almost double than yours can you please help me in optimization

Last edit: 2015-07-21 18:29:11
2015-07-19 22:21:28 :?ToRpiDo
@ivar.raknahs & @[Lakshman] :: btw what should i do to make it faster

Last edit: 2015-07-19 22:23:25
2015-07-19 21:59:02 :?ToRpiDo
After 10 WA's & TLE's.....finally green :-)
thnx @ivar.raknahs :-)

Last edit: 2015-07-19 22:07:53
2015-07-19 17:05:40 Vaporeon
2 days. finally AC ! :D :D
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.