Introduction

“Boring Factorials” is usually the competitive-programming version of a modular factorial problem: compute n! mod p efficiently when p is prime and n may be very large. A direct factorial loop is too slow when n is close to p, so the standard trick is to use Wilson’s theorem and modular inverses. The problem is only “boring” once you see that number-theory shortcut.

Why the Naive Solution Is Too Slow

The straightforward implementation multiplies every integer from 1 through n and reduces modulo p.

1def factorial_mod_naive(n: int, p: int) -> int:
2    result = 1
3    for x in range(1, n + 1):
4        result = (result * x) % p
5    return result

This works for small inputs, but if n is huge, it is too slow. In contest problems, n is often close to p, which means looping all the way up to n defeats the purpose.

Use the Prime-Modulus Shortcut

When p is prime, Wilson’s theorem says:

(p - 1)! ≡ -1 (mod p)

Now split (p - 1)! into two parts:

(p - 1)! = n! * (n + 1) * (n + 2) * ... * (p - 1)

Rearranging modulo p gives:

n! ≡ -1 / ((n + 1)(n + 2)...(p - 1)) (mod p)

In modular arithmetic, division means multiplying by an inverse. Because p is prime, the inverse of x modulo p is x^(p-2) mod p by Fermat’s little theorem.

That gives a much better strategy when n is close to p: multiply only the tail from n + 1 to p - 1, then invert it.

Handle the Easy Case First

If n >= p, then n! contains p as a factor, so:

n! mod p = 0

That makes the first branch trivial.

1def boring_factorial(n: int, p: int) -> int:
2    if n >= p:
3        return 0
4    # handle the harder case n < p next

This check matters because it saves work and avoids applying Wilson’s theorem in the wrong context.

Efficient Python Implementation

Python’s built-in pow supports modular exponentiation, which makes modular inverses compact and fast.

1def boring_factorial(n: int, p: int) -> int:
2    if n >= p:
3        return 0
4
5    tail_product = 1
6    for x in range(n + 1, p):
7        tail_product = (tail_product * x) % p
8
9    inverse_tail = pow(tail_product, p - 2, p)
10    return (-inverse_tail) % p
11
12
13print(boring_factorial(3, 7))   # 6 because 3! mod 7 = 6
14print(boring_factorial(5, 11))  # 10 because 5! mod 11 = 10

The key win is that the loop runs over p - 1 - n values, not n values. That is a major improvement when n is very close to p.

Why the Formula Works in Practice

Take n = 5 and p = 11.

We know:

10! ≡ -1 (mod 11)

And:

10! = 5! * 6 * 7 * 8 * 9 * 10

So:

5! ≡ -1 / (6 * 7 * 8 * 9 * 10) (mod 11)

The code computes exactly that denominator, finds its modular inverse, and multiplies by -1 under modulo 11.

This is not a heuristic. It is a direct consequence of Wilson’s theorem and modular inverses.

When This Trick Is the Right One

This method is especially good when:

• 'p is prime'
• 'n < p'
• 'n is close to p'

If n is small, the naive factorial may be fine. If p is not prime, the inverse trick based on x^(p-2) is not generally valid, and you need a different method.

In other words, this is a specialized contest technique, not the universal answer to every factorial-modulo question.

Common Pitfalls

A common mistake is applying the Wilson-theorem shortcut when p is not prime. The logic depends on prime modulus arithmetic.

Another issue is forgetting the n >= p case. In that situation, the answer is immediately 0, and trying to use the inverse-based formula adds needless work or confusion.

Developers also sometimes compute pow(tail_product, -1, p) mentally and then translate it incorrectly. In Python contest solutions, pow(tail_product, p - 2, p) is the standard and portable form for prime-modulus inversion.

Finally, this optimization helps when p - n is small. If n is far from p, there may be less benefit compared with a direct loop.

Summary

• The “Boring Factorials” trick is about computing n! mod p efficiently under a prime modulus.
• If n >= p, the answer is 0 immediately.
• When n < p, Wilson’s theorem lets you transform the problem into an inverse of the tail product from n + 1 to p - 1.
• Python’s pow(x, p - 2, p) makes modular inverse computation concise.
• This method is specialized for prime p, so do not apply it blindly to composite moduli.