Find an algorithm to compute $(1! \cdot 2! \cdot3!\cdots n! ) \,\%\, x$.

Question

You need to find the product of first n factorials $1! \cdot 2! \cdots n!$ modulo $109546051211.$ $1 \le n \le 10^7$. I need a fast algorithm for this.

Answer 1

Since $109546051211 = 186583 \cdot 587117$ and both $186583$ and $587117$ are less than $10^7$, the result is $0$.

Answer 2

If $n\ge587117$ then the result is 0, as lhf mentioned.

Otherwise, set the total to 1 and $f$ to 1 and loop from $k=2$ to $n$. At each step, multiply $f$ by $k$ and then multiply the total by $f$, reducing both mod 109546051211.

As a simplification, if $n\ge186583,$ you can work mod 587117 only and use the Chinese Remainder Theorem to get the final result.