<s>[INST] Simple way to calculate $n! \pmod p$ I have the exercise "Calculate $10! \pmod{13}$".
I have the following two approaches to solve the exercise:


*

*Brute force approach


$$
1! \equiv 1 \pmod{13} \\
2! = 2 \cdot 1! \equiv 2 \cdot 1 \equiv 2 \pmod{13} \\
3! = 3 \cdot 2! \equiv 3 \cdot 2 \equiv 6 \pmod{13} \\
\cdots \\
10! = 10 \cdot 9! \equiv 10 \cdot 11 = 110 = 8 \cdot 13 + 6 \equiv 6 \pmod{13}
$$


*Approach using Wilson's theorem:


Wilson's theorem states that
$$p \in \mathbb{P} \implies (p-1)! \equiv -1 \pmod p$$
For my exercise:
$$13 \in \mathbb{P} \implies \\
(13-1)! = 12! = 10!\cdot 11 \cdot 12 \equiv -1 \pmod{13} \implies \\
10! \equiv -(11 \cdot 12)^{-1} \pmod{13}
$$
Using Fermat's little theorem
$$
a^p \equiv a \pmod p \implies a^{p-2} \cdot a \cdot a \equiv a^{-1} \cdot a \cdot a \pmod p \implies a^{p-2} \equiv a^{-1} \pmod p \\
$$
For my exercise:
$$10! = -(11 \cdot 12)^{-1} \equiv \\
-(11 \cdot 12)^{13-2} = -(11 \cdot 12)^{11} \equiv \\
-(-2 \cdot -1)^{11} = -2^{11} = \\
-2^6 \cdot 2^5 \equiv 1 \cdot 2^5 = \\
32 \equiv 6 \pmod{13} \\
$$
Both approaches look quite bulky.
In the first method I have to make $O(n)$ multiplications.
In the second method I have to make $O(p-n)$ multiplications which is smaller than in the first method, but also can be huge number for big $p$ and $n$.
Is there a way to improve my solution?
Is there an efficient way to calculate $n! \pmod p$ for big $n$ and $p$?
 [/INST] Start with your Wilson's Theorem approach but finish off differently.  Note that $12\equiv -1$ and $11\equiv -2 \pmod{13}$ and that these two numbers have easy inverses $(-2)(-7) \equiv 1$ and $(-1)(-1) \equiv 1 \pmod{13}$, so 
$$10! \equiv -(11)^{-1}(12)^{-1} \equiv -(-2)^{-1}(-1)^{-1} \equiv -(-7)(-1) \equiv 6 \pmod{13}.$$
</s>