BORING - Boring Factorials (Reloaded)

no tags 

Factorial is one of the most attractive word this week, it is proposed to reload a famous problem. Is it so boring ?

Sameer and Arpit want to overcome their fear of Maths and so they have been recently practicing Maths problems a lot. Aman, their friend has been helping them out. But as it goes, Sameer and Arpit have got bored of problems involving factorials. Reason being, the factorials are too easy to calculate in problems as they only require the residue modulo some prime and that is easy to calculate in linear time. So to make things interesting for them, Aman - The Mathemagician, gives them an interesting task. He gives them a prime number P and an integer N (not so) close to P, and asks them to find N! modulo P. He asks T such queries.

Input

The first line of input contains an integer T, the number of test cases.
On each of the next T lines, your are given two integers N, and P a prime number.

Output

For each test case, you have to print N! modulo P.

Example

Input:
3
2 5
5 11
21 71
Output:
2
10
6

Constraints

0 < T < 10^4
0 < N < 4×10^18
1 < P < 4×10^18, a prime number
Abs(N-P) < 10^4

Problem designed to be solvable using some 'slow' languages like Python (333B of code). It is highly recommended to solve in a very fast way the original problem! Basic solution, even in fast language should give TLE.
Time limit is set as sqrt(correct × basic). The "basic" code gave me 0.00s to the original problem with slow IO.
If you don't find this reload edition hard enough, please consider the challenge edition with more serious constraints.
;-) Have fun.


hide comments
Avik Sarkar: 2018-06-03 15:13:05

HI. I used Willson's theorem + Inverse Modulo . Can anyone suggest me a hint of any faster way. Here is my submission: ************** edited ********* ( Please edit if it violates rules. But please give a hint. )

=(Francky)=> No hint here ; except : try to solve various problems to find some hints.

=>(Avik Sarkar) => I solved the first and easy one using the way I mentioned above. But solving in the same way I got TLE. Can you just tell me am I in a correct way or not ?

Last edit: 2018-06-03 18:28:14
free mind ;): 2015-09-26 09:16:29

@Francky sir can you tell why i am getting runtime error , i am new in python, is this because range function or something else and can you please tell why my c++ solution giving WA . :)

vishu: 2015-08-13 03:00:17

@Francky sir,can you please tell me for what test cases it is giving wrong answer.Is it a specific input or it is giving wrong answer due to overflow? submission id-14880828

=(Francky)=> You have WA for almost all input ; good luck.

Finally Ac! learnt python to do this

Last edit: 2015-08-29 23:01:24
Curiosa: 2015-03-18 18:13:33

@Francky, could you please check my solution? Is the idea behind my solution "basic" (in your terms)? My solution is still slow compared to others, is this because of Java?

(Francky) => Java could be faster than Python for that task, and your method could give TLE with Python. It is a basic one, using java (or Python) it is easy to implement some nice improvements. Good luck.

@Francky, I have developed some of my ideas, can I further develop my idea or do I need to come up with something completely different to achieve lower time limit? can you give me any hints?

Last edit: 2015-03-25 13:58:16
ivar.raknahs: 2014-11-04 16:14:49

@francky=> can u tell me where my code fails (id:12812179) and can i get AC with this kind of approach?. Thanks
--ans(Francky)--> You have a slow but correct python code, you'll can easily find some troubles in your C++ code, like negative outputs and most of WA cases. Good luck.

Last edit: 2014-11-04 20:54:35
Tarun Garg: 2014-07-27 19:03:12

@Francky where my code is falling out..?
is there any chances to get Ac..?
--ans(Francky)--> Not with this kind of code. Sorry... You should try some brute force with Python, and find some new ideas to get AC in time.

Last edit: 2014-07-27 21:12:20
[Lakshman]: 2014-03-09 15:09:59

@Francky Finally Accepted with C++ but with worst running time.
--ans(francky)--> I see that, but those experiments will give solutions to get AC in Extended or more points in Challenge ; you're doing right things.
Lakshman--> Thanks I will do that.

Last edit: 2014-03-09 15:37:26
anurag garg: 2014-03-08 07:54:53

Francky sir I am getting WA but I got AC on DCEPC11B in 0.02 sec
can you tell me where my code fails and is there any chance to get AC in time?
submission id:11208025
thanks
--ans(francky)--> You used a basic method, but a fast language ; it's possible but hard to get AC. You have overflow problems (you should try FIB64 for that, in Python and after in C/C++ ). It can be simpler to get AC here with a really different method. Good luck.

--anurag-> thanks for the suggestion sir i will try to solve

Last edit: 2014-03-08 09:08:24
[Lakshman]: 2014-03-04 19:21:54

@Francky is there any chance of AC with my approach?
--ans(francky)--> Your approach seems too simple here to get AC in time. You should get 0.00s easily on the original problem before trying this one. Just an advice ;-)

Lakshman-->PIKE really helped me.
--ans(francky)--> Good job, stage 1 done. Now you can try new ideas ;-) with the challenge edition, or try to get AC at BORING2.

Lakshman-->Right now I have no Idea how to approach BORING2 But I will keep trying. One thing I would say your problems are awesome.
--ans(Francky)--> Thanks for your appreciation.

Last edit: 2014-03-06 10:53:16
Francky: 2014-03-04 13:58:39

This reload edition wasn't hard enough, although not an easy one.
Please consider the challenge edition with more serious constraints.
Have fun ;-)

Last edit: 2014-03-04 20:07:22

Added by:Francky
Date:2014-03-03
Time limit:2.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:DCEPC11B