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: 2017-11-09 14:37:42

@Michael Kharitonov
Yes, to be exact, we need the complexity you wrote for the polynomial multiplication in Z/PZ. In this problem, the factor O(log P) is disregarded because it might be confusing.

As for the polynomial interpolation, the tag might be misleading; intended solutions do not use it explicitly.

Last edit: 2017-11-09 14:45:24
Michael Kharitonov: 2017-11-09 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)
Let I(n) be the time for polynomial interpolation of size n. Then I(n)~M(n)*log(n).
I got complexity ~sqrt(P)*(log(P)^3). Where did I gain 2 extra logs?
P.S. got rid of log(n) in interpolation.

Last edit: 2017-11-12 01:38:14

Added by:Min_25
Date:2017-10-20
Time limit:10s-15s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All