Try what’s described here. https://mirror.codeforces.com/blog/entry/63491

I don't know the actually way to implement this problem but you can loop N from 1 to 10^11 and calculate n!%p through this formula: (a * b) % c = ((a % c) * (b % c)) % c; and prefix sum. Then store them into an array. If you implement the problem with these operations, you can get the answer in about 3 hours.

Divide&Conquer + NTT + FFT

The problem is too hard that it is of no use to let a cyan to solve the problem! HAHAHAHA

I have a solution First,build a polynomial of n*(n+1)*(n+2)*(n+3).....*(n+sqrt(p)) Then use we can get the value of the polynomial at 1,sqrt(p)+1,2sqrt(p)+1.... Then we can calculate the rest of part(not exceed sqrt(p)) using bruteforce.

We can construct a polynomial :

$$$F(x)=\prod_{i=1}^{\lfloor\sqrt n\rfloor}(x+i)$$$

And then we have :

$$$n!=\bigg(\prod_{i=n-{\lfloor\sqrt n\rfloor}^2}^{n}i\bigg)\cdot\prod_{i=0}^{\lfloor\sqrt n\rfloor}F(i\cdot \lfloor\sqrt n\rfloor)$$$

For $$$\prod_{i=n-{\lfloor\sqrt n\rfloor}^2}^{n}i$$$ , we can calculate it use brute force.

For $$$\prod_{i=0}^{\lfloor\sqrt n\rfloor}F(i\cdot \lfloor\sqrt n\rfloor)$$$ , we can use fast polynomial multipoint evaluation to calculate. (https://cs.stackexchange.com/questions/60239/multi-point-evaluations-of-a-polynomial-mod-p)

Sorry for my poor English.

if p is prime then the problem is pretty much implementation of wilson's theorem.

in mind