BORING3 - Boring Factorials (Ultimate)

no tags 

Factorial is one of the most attractive word this week, it is proposed to reload a famous problem. Is it so boring ?
As the reload edition wasn't hard enough, we'll make a challenge edition with harder constraints.


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 input contains several lines. Probably, you'll can't process all ; please exit your program before the time limit.
Warning : To allow more input, its presentation is different than in other BORING* problems.
On each line, your are given two integers D (delta), and P a prime number.

Output

For as many test cases you can, you have to print (P-D)! modulo P.

Example

Input:  warning, it's different from other BORING* input.
3 5
6 11
50 71
[...]
Output:
2
10
6
[...]

Constraints

0 <= D <= 10^6
1 < P < 10^100, a prime number

For your information : With Python3, my "brute force" got 435 points, my first code for (BORING1/2) got 1631 points ; my new BORING3 code got 2772 (edit 4041) points to be challenged.
;-) Have fun.

Edit(12/II/2017) Now the MasterJudge takes time into account if you reach the limit of input file : There's only 300000 lines.


hide comments
Min_25: 2014-03-07 16:44:54

I agree too.
--ans(Francky)--> I've yet computed 200000 big primes, and checked all by hands, tomorrow I should be at 300000 and make changes.

Last edit: 2014-03-06 16:51:25
Francky: 2014-03-07 16:44:54

Wahoo!!! OK, now I must admit I have to reconsider your offer : I will generate more primes again, and probably put P and Delta in input. I think you agree for that, Min_25 too (as the two lonely solver for now).
(gerrob)Yes, I agree with you.

Last edit: 2014-03-05 22:26:58
Robert Gerbicz: 2014-03-07 16:44:54

Just a suggestion: if the input would be
N-P P for each line than you could upload roughly twice more lines. (not speaking about that the reading would be faster on slow languages also).
--ans(Francky)--> It's true, but keep the initial description can be fine. Read input cost eps time compared to the question, whatever the language. I will upload up to 100000 lines and that seems unreachable (my next code should turn at 5000 points when debugged ; EDIT : no it's even slower :-(( , I'm still at 2772). EDIT2 : Faster now : 3429. EDIT3: 4041.

Last edit: 2014-03-05 14:19:42

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