N! mod P (1)

Given a positive integer $N$ and a prime $P$ greater than $N$, find the remainder when $N!$ is divided by $P$.

The first line contains $N$ and $P$ separated by a space.

Find the remainder when $N!$ is divided by $P$.

• $1 \le N < P \le 10^8$
• $P$ is prime

The solution the setter intended and wrote runs in about 1500ms.

The fast solution the setter wrote runs in about 60ms.