I am trying to understand and solve the following problem :

Sameer and Arpit want to overcome their fear of Maths and so they have been recently practicing Maths problems a lot. Aman, their friendhas been helping them out. But as it goes, Sameer and Arpit have gotbored of problems involving factorials. Reason being, the factorialsare too easy to calculate in problems as they only require the residuemodulo some prime and that is easy to calculate in linear time. So tomake things interesting for them, Aman - The Mathemagician, gives theman interesting task. He gives them a prime number P and an integer Nclose 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 forclarity)

Output:

Output exactly T lines, containing N! modulo P.

Example
Input:
32 55 1121 71Output:
2106Constraints:1 <= T <= 10001 < P <= 2*10^91 <= N <= 2*10^9Abs(N-P) <= 1000

now to this I wrote a solution :

def factorial(c):
n1=1
n2=2
num=1
while num!=c:n1=(n1)*(n2)n2+=1num+=1
return n1for i in range(int(raw_input())):n,p=map(int,raw_input().split())print factorial(n)%p

but as you can see this is inefficient solution so I started searching for a better solution than I came to know that this can be solved using wilson's and fermet's theorem.But I am unable to understand what the author is trying to say He says:

**In number theory, Wilson's theorem states that a natural number n > 1 is a prime number if and only if

Now from this we can write:

(p-1)!   ≡  -1 (mod p)1*2*3*.........*(n-1)*(n)*..............*(p-1)  ≡   -1 (mod p)n!*(n+1)*...........*(p-1)   ≡   -1 (mod p)n!  ≡    -1*[(n+1)*...............(p-2)*(p-1)]^-1 (mod p)let a=[(n+1)*...............(p-2)*(p-1)]son!≡-1*a^-1(mod p)From Fermat's Theorem:a^(p-1) ≡ 1(mod p)multiply both side by a^-1a^(p-2)  ≡ a^-1(mod p)now simply we have to find a^(p-2) mod p

**

so I implemented this:

def factorial1(n,p):            # to calculate  a=[(n+1)*...............(p-2)*(p-1)]
n0=n+1
n1=n0+1
while n1<=(p-1):n0=n1*n0n1+=1
return n0
# print nf(2,5)for i in range(10):n,p=map(int,raw_input().split())if n>p:print 0elif n==p-1:print p-1else:print (factorial1(n,p)**(p-2))%p   #a^(p-2) mod p

But from the output which I am getting I think I misunderstood what he wrote .Can someone tell me what is he telling me to calculate and how do I write the code for what he is saying.

This is not a straight-forward application of the Wilson's theorem. Along with it use the following facts:

• if n >= p then n! = 0 (mod p)
• if n < p then n! = (p-1)!/[(n+1)(n+2)..(p-1)]. Now use the fact that (p-1)! = -1 (mod p). All that is left for you to find is the modular multiplicative inverse (using extended Euclidean algorithm for example) of the numbers n+1, n+2, ... , p-1 which number is at most 1000 from the fact that abs(n-p) <= 1000. Multiply (p-1)! = -1 (mod p) with all modular multiplicative inverse of the numbers n+1, n+2, ... , p-1 and you get the answer. (as John Coleman pointed out you could also do a inverse of the the product and not product of the inverse as an optimization)

In your case n=2, p=5 (just to see how it works)

n! = 2! = 4!/(3*4) = (-1)*2*4 = 2 (mod 5)# 2 is modular inverse of 3 since 2*3 = 1 (mod 5)
# 4 is modular inverse of 4 since 4*4 = 1 (mod 5)