FACTMODP  Factorial Modulo Prime
Find $N!$ modulo $P$.
Input
The first line contains $T$ ($1 \le T \le 100,000$), the number of test cases.
Each of the next $T$ lines contains two integers $N$ ($0 \le N \le 10^{11}$) and $P$ ($2 \le P \le 10^{11}$), where $P$ is a prime.
Output
For each $N$ and $P$, output $N!$ modulo $P$.
Constraints
For each input file, It is guaranteed that (the sum of $\sqrt{P}) \le 320000$.
Example
Input
3 1000 9907 1000000 9999907 10000000000 99999999907
Output
4494 3354924 40583077821
Note
 Probably, $O(P)$ solutions will not pass.
 Intended solutions have a complexity of about $O(\sqrt{P} \log{P})$
 My solution runs in 0.5 seconds for each input file.
hide comments
Min_25:
20171109 14:37:42
@Michael Kharitonov


Michael Kharitonov:
20171109 13:22:52
Let M(n) be the time to multiply 2 polynomials of degree n in Z/PZ. Then M(n)~n*log(n)*log(nP)

Added by:  Min_25 
Date:  20171020 
Time limit:  10s15s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 