## 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. 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