Calculating large Bell number modulo a composite number

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 $n$th Bell number modulo a prime number greater than $10^7$ in $O(n)$ arithmetic operations, 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?

Solution 1:

For this problem, it's more convenient to use the formula for Bell numbers expressing them as the sum of Stirling numbers of the second kind: $$B_n=\sum_{k=0}^n \left\{ {n \atop k} \right\}.$$ This formula does not involve any divisions and can be evaluated modulo any given $m$, provided that we can compute $n$-th row of Stirling numbers modulo $m$.

Stirling numbers modulo $m$ can be computed row-by-row (hence keeping only two rows in the memory at once) using the recurrence: $$\left\{{n+1\atop k}\right\} = k \left\{{ n \atop k }\right\} + \left\{{n\atop k-1}\right\}\quad (k>0)$$ with the initial conditions $\left\{{ 0 \atop 0 }\right\} = 1$ and $\left\{{ n \atop 0 }\right\} = \left\{{ 0 \atop n }\right\} = 0$ for any $n>0$.