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?
 A: 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$.
A: As mentioned in the comment, large Bell number modulo factorials can be calculated efficiently using following congruence.
$$\sum_{k=0}^{n}D_{n,k}B_{m+k}\equiv 0\ (\textrm{mod}\ n!)$$
$$D_{n+1,k}=D_{n,k-1}-(n+1)D_{n,k}-nD_{n-1,k}$$
$n \geq 0,k \geq 0$
$D_{0,0}=1$
$D_{n,k}=0,\hspace{5 mm}k>n,k<0$
It takes $O(MN)$ time to calculate $M^{th}$ Bell number modulo $N!$.
