Calculating large Bell number modulo a composite number

Question

I have been trying to solve http://www.javaist.com/rosecode/problem-511-Bell-Numbers-Modulo-Factorial-askyear-2018

It is not an ongoing contest problem.

We can calculate $10^7$th Bell number modulo a prime number greater than $10^7$ in $O(n)$ using this formula $$B_n=\sum_{k=1}^{n}\frac{k^n}{k!}\sum_{j=0}^{n-k}\frac{(-1)^j}{j!}$$ We can store the partial inner sum for future use, without calculating again and again. For example $B_{10^7}$ $\text{mod}$ $1000000007$ $=29987405$.

But in the problem the modulus is $30!$, so we can't do modular inverse operations. I tried to reduce the formula to $$B_n=\sum_{k=1}^{n}\frac{k^n!(n-k)}{k!(n-k)!}=\frac{1}{n!}\sum_{k=1}^{n}\binom{n}{k}k^n!(n-k)$$ $!n$ denotes subfactorial function.

I am stuck here. Can anyone help?

I asked the same question at https://math.stackexchange.com/questions/2919174/calculating-large-bell-number-modulo-a-composite-number, so far I haven't got any response.

Answer 1

Maybe you can use the ordinary generating function for the Bell numbers \begin{equation*} \sum_{n\geq 0} B_nx^n=\sum_{n\geq 0} \frac{x^n}{(1-x)(1-2x)\cdots(1-nx)} \end{equation*} The use of this generating function overcome the difficulty of inverting $\pmod{30!}$, but I am not sure that the series is suitable for efficient computations.