SPOJ.com - Problem POWFIB2

POWFIB2 - Fibo and non fibo(Hard)

no tags

The problem is simple. Find (a^b) % MOD.

where, a = Nth non-Fibonacci number, b = Nth Fibonacci number.

Consider Fibonacci series as 1, 1, 2, 3 ...

Input

First line contains T, the number of test cases. Each of the next T lines contains two numbers N and M where M is a prime number.

Output

Print T lines of output where each line corresponds to the required answer.

Example

Input:
3
3 1000000007
2 13
1 13

Output:
49
6
4

Explanation

For N = 3: 3rd non Fibonacci number = 7, 3rd Fibonacci number = 2. Answer = (7^2) % 1000000007 = 49

For N = 2: 2nd non Fibonacci number = 6, 2nd Fibonacci number = 1. Answer = (6^1) % 13 = 6

For N = 1: 1st non Fibonacci number = 4, 1st Fibonacci number = 1. Answer = (4^1) % 13 = 4

If you are getting TLE here you may try easy version of this POWFIB.

Constraints

1 <= T <= 50000

1 <= N <= 1e16

2 <= M <= 1e18, and M is a prime number.

Note:: My best time with C++ with fully optimized code is 1.18s.

Have fun :)

Submit solution!

hide comments

< Previous 1 2 Next >

	surya97: 2015-11-04 03:14:18 @Lakshman now i have changed my fibonacci calculation algo. But i got WA in test case 4. So can you tell me whether that algo is right and a small modification will get it accepted? ==(Lakshman)=>This is hard, try other easy Fibonacci problems. Last edit: 2015-11-05 04:56:43
	surya97: 2015-11-03 12:17:53 @lakshman is the mulmod you sent was multiplication using repetitive modular addition ? Still it is wrong after test case 4. =(Lakshman)=>I told you you have overflow issue. now overflow inside Fibonacci computation. Even if you correct that your code will give TLE. Last edit: 2015-11-03 20:04:56
	surya97: 2015-11-03 04:43:02 I think this question is above my level. I have implemented modular multiplication "m = aq + r q = [m / a] r = m mod a az mod m = a(z mod q) − r[z / q] " still getting WA after test case 4 =(Lakshman)=> Your mulmod finction is wrong. use this http://ideone.com/O5Pq82 Last edit: 2015-11-03 10:42:11
	surya97: 2015-11-01 16:23:56 @Lakshman , i have changed the modular exponentiation function. Still giving WA after 4th testcase. Is the function still causing overflow? for the test case you gave to mohib my solution is giving answer 97794046510201901 ==(Lakshman)=>Your output is wrong and you need to change your modular exponentiation , hint use modular multiplication while multiplying . Last edit: 2015-11-02 17:55:06
	surya97: 2015-11-01 05:52:02 Is the overflow occuring in calculating nth fibonacci or nth non fibonacci or modular exponentiation? @Lakshman please could you tell me where it is happening? =(Lakshman)=> in this function ll modular_pow(ll base, ll exponent,ll m) Last edit: 2015-11-01 11:23:21
	surya97: 2015-10-30 17:04:19 why my solution is taking 256M and i could not get why it is failing after test case 4. @Lakshman can you see my code and tell me if the functions i used are suitable or not? ==(Lakshman)=>I think you are using map and it is taking the memory which you have mention. Second this you getting wrong answer because of overflow. Last edit: 2015-10-31 21:49:33
	:.Mohib.:: 2015-07-22 19:30:05 Is the answer is 93912501657209262?? =(Lakhman)=>No its 98581822110729285 Last edit: 2015-07-22 20:08:02
	:.Mohib.:: 2015-07-22 17:01:29 Not able to find it....can you help me??...:( =(Lakshman)=> Test case 5915220977316237 100000000000000021 Last edit: 2015-07-22 18:19:19
	:.Mohib.:: 2015-07-22 12:39:39 Last edit: 2015-07-22 20:06:59
	Pulkit Singhal: 2015-07-21 18:18:57 Easy One :) POWFIB in Classical and POWFIB2 in Tutorial, Amazing :P Last edit: 2015-07-21 18:23:45

Submit solution!

Added by:	[Lakshman]
Date:	2015-07-18
Time limit:	10s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64 JS-MONKEY
Resource:	POWFIB