Firstly, we denote the multiplicative inverse of x mod p as inv(x,p).
- use dp method to calculation x! mod p for x=1 ~ n (1<=n<p, p is some prime)
- calculate inv(n!,p) utilize Extended Euclidean algorithm.
- use dp again to calculate inv(x!,p) for x=n-1 ~ 1 with the fact inv(x!,p) * x = inv((x-1)!, p)
- now, if we want to now inv(x,p) for some x in [1,n], we only need to calculate (x-1)! * inv(x!,p)