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
priyank: 2015-12-15 19:49:01

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

mukesh227: 2015-10-30 19:33:55

after 4 WA finally AC!!!!!

Last edit: 2015-10-30 19:34:36
surya97: 2015-10-27 08:00:59

hurray! got accepted. :)
Feeling good

Last edit: 2015-10-27 08:01:28
surya97: 2015-10-26 19:38:32

@author: please help why i am getting wrong answer after case 15. many WAs.
This is my code. http://ideone.com/mlnPHw
please help me :(
Tried all data types. Still could not figure it out.

Last edit: 2015-10-26 19:52:39
surya97: 2015-10-26 14:29:29

i am getting WA after 12th test case @ivar.raknahs

Last edit: 2015-10-26 14:33:19
Aditya Kumar: 2015-10-23 08:33:16

Wrong Data Type costed me couple of WA!!

tinneminy: 2015-08-22 12:22:24

@ivar.raknahs : Can you plz check my submission ID-14951756. I already got more than 8 WA. Don't know where i m wrong.

weathervane: 2015-08-21 21:20:56

@ivar.raknahs I'm confused. The time limit is 1 second, but today answers taking 3 seconds were accepted.

-reply-> the time that judge gives you is the total time taken for all input file

Last edit: 2015-09-03 16:25:51
Dune: 2015-08-17 13:28:58

@ivar.raknahs : testcases have been updated with cases where N>10^7, but previous submissions haven't been rejudged, you'll have to rejudge it.
(I've constated my submission of 2015-07-26 hasn't been rejudged)

Last edit: 2015-08-17 20:47:06
kartikay singh: 2015-08-05 14:21:26

@ivar.raknahs : Can you plz check my submission I think my algo is correct :(


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