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 >

	:.Mohib.:: 2015-07-21 16:29:16 @Lakshman, long long is enough to store the value of b in c language?? Plzz help.... =(Lakshman)==>Every thing will fit to long long. Last edit: 2015-07-21 16:33:47
	ivar.raknahs: 2015-07-19 17:42:46 @[Lakshman]: Could you please add a link to the powfib version so that the users who find this question hard at first ,may try the easier version? It's fully up to you. Last edit: 2015-07-20 09:05:58
	[Lakshman]: 2015-07-19 11:58:06 Now Time Limit is 2* my slow python solution. =(Francky)=> Now visible. Please add again in constraints that M is prime, this info is crucial and should be given in constraints. Thanks for your efforts. Last edit: 2015-07-19 12:24:11
	Francky: 2015-07-19 11:21:12 @Wisfaq : well explained. Thanks. Now, the fact that M is a prime number change a bit things. But, the problem is still MULMOD dependant, and as you "restrict" to fast languages with strict time limit, the problem remains hidden. When you create a problem, you have to find the bottleneck, and ask you "is it a new problem ?", or "can I avoid this bottleneck, to focus on the new specific problem ?". A problem shouldn't be a "hard" classic trick with a cover with obvious stuff. You can make this problem visible, imho, with two options : either M fit in 31-bit container, or time limit is at least 2× a decent slow_language_time (eg, with Python where MULMOD isn't a problem). But, in fine, visible, this problem would remain in tutorial. I hope you understand. =(Lakshman)=>I accept that the TL is strict But even with strict time limit we can get AC with Python. However I will increase the Time Limit. Last edit: 2015-07-19 11:56:01
	wisfaq: 2015-07-19 09:44:58 @Lakshman: as you don't state that M is prime it's necessary to factor M. as 2<=M<=1e18 factorising M makes this problem related to FACT1. If M is always prime you should have stated so. Remains the fact that there are loads of (a^b)%M problems. ==(Lakahman)==>Okay I have updated the Problem statement now. Thanks. Last edit: 2015-07-19 10:39:33
	[Lakshman]: 2015-07-19 04:39:33 @Francky may I know the reason of hiding this problem and how this problem is related with FACT1. Please explain. Last edit: 2015-07-19 13:49:53
	Francky: 2015-07-18 22:10:53 I think there's enough "(a^b) % M" problems, and here it's again a FACT1 dependant one, the other parts are quite obvious. Problem hidden.
	:.Mohib.:: 2015-07-18 20:48:00 @Lakshman can you please give some hint about how to handle overflow for the value of b while calculating (a^b)% MOD??Thanks.... Last edit: 2015-07-18 21:08: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