FACTMODP - Factorial Modulo Prime


Find N!N! modulo PP.

Input

The first line contains TT (1T100,0001 \le T \le 100,000), the number of test cases.

Each of the next TT lines contains two integers NN (0N10110 \le N \le 10^{11}) and PP (2P10112 \le P \le 10^{11}), where PP is a prime.

Output

For each NN and PP, output N!N! modulo PP.

Constraints

For each input file, It is guaranteed that (the sum of P)320000\sqrt{P}) \le 320000.

Example

Input

3
1000 9907
1000000 9999907
10000000000 99999999907

Output

4494
3354924
40583077821

Note

  • Probably, O(P)O(P) solutions will not pass.
  • Intended solutions have a complexity of about O(PlogP)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