I'm trying to find the fastest way to compute $$\sum_{i = 0}^n \frac{n!}{i!} \mod p$$ where one can suppose that $p$ is a prime number.
Given that $n$ can be a huge number, the only simple way I can think of now is a $O(n)$ algorithm. Can we do better than that ?
Note that $u_n=\sum_{i = 0}^n \frac{n!}{i!} = \lfloor n!e \rfloor$ for $n >0$ and that $u_{n+1} = n(u_n+1)$, if that helps.