DCEPC11B  Boring Factorials
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 close to P, and asks them to find N! modulo P. He asks T such queries.
Input
First line contains an integer T, the number of queries asked.
Next T lines contains T queries of the form “N P”. (quotes for clarity)
Output
Output exactly T lines, containing N! modulo P.
Example
Input: 3 2 5 5 11 21 71 Output: 2 10 6Constraints:
1 <= T <= 1000
1 < P <= 2*10^9
1 <= N <= 2*10^9
Abs(NP) <= 1000hide comments
bikrambiswas:
20210111 16:23:52
This is a great problem of(wilson+fermit) theorem


yzs:
20200925 14:10:39
good ques


smso:
20200925 10:46:09
more testcases:


profesir:
20200902 18:21:09
don't use code from cpalgorithm..


nadstratosfer:
20200715 20:18:53
There's something strange about the judge used here, wasted half an hour yesterday because an assert on n < p wouldn't trigger a NZEC. Tried without looking up anyone else's theorem several times last few years, had to give up on that but still passed with logic more straightforward than what others seem to be doing. 

saint_sharan:
20200614 18:43:36
My code is giving TLE, although I used the same algorithm given at CPAlgo page, including the condition when (n>=p). What's the method to remove that TLE? 

kabbo25:
20200426 03:00:10
Willson thoerem+check when n is greater than p then n goes up to p1


sajalagrawal14:
20190729 12:48:35
ac in five go . dont use recusive fast modulo , use iterative 

abhimanyu_1998:
20190704 11:51:15
ac in one go


ashu12_chi:
20190524 14:27:30
@anirudnits 502781432 answer from my AC

Added by:  dce coders 
Date:  20131001 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  C CSHARP C++ 4.3.2 CPP C99 HASK JAVA PASGPC PASFPC PYTHON PYTHON3 PY_NBC 
Resource:  Own Problem 