SPOJ.com - Problem POWFIB2

POWFIB2 - Fibo and non fibo(Hard)

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!

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

hide comments

2015-07-21 16:29:16 :.Mohib.:
@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

2015-07-19 17:42:46 ivar.raknahs
@[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

2015-07-19 11:58:06 [Lakshman]
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

2015-07-19 11:21:12 Francky
@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

2015-07-19 09:44:58 wisfaq
@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

2015-07-19 04:39:33 [Lakshman]
@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

2015-07-18 22:10:53 Francky
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.

2015-07-18 20:48:00 :.Mohib.:
@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