How to calculate a Bell number (Bell[n] mod 95041567) quickly enough? How to calculate a Bell number (Bell[n] mod 95041567) quickly enough?
Here n maybe very big as 2^31.
Bell number is http://oeis.org/A000110 
 A: Wikipedia (https://en.wikipedia.org/wiki/Bell_number) states Touchard's congruence for a prime power $p^m$ as
$$B_{p^m + n} = m B_n + B_{n+1} \pmod{p}$$
Using this and the Chinese remainder theorem you should be able to calculate the numbers pretty quickly.
More details: One straightforward way is to take $m=1$ in the congruence. Then we are left with the linear recurrence relation $B_{p+n} = B_n + B_{n+1}$. This can be solved efficiently by transforming it into a matrix and using exponentiation by squaring (https://en.wikipedia.org/wiki/Exponentiation_by_squaring). For example: Let $p=5$, then
$$\begin{pmatrix} B_{n+1} \\ B_{n+2} \\ B_{n+3} \\ B_{n+4} \\ B_{n+5} \end{pmatrix}=\begin{pmatrix} 0 & 1 & 0 & 0 & 0\\0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0& 1 & 0 \\0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 \end{pmatrix} \begin{pmatrix} B_n \\ B_{n+1} \\ B_{n+2} \\ B_{n+3} \\ B_{n+4} \end{pmatrix}.$$
To calculate $B_n \pmod{5}$ for some big $n$ just raise the matrix in the middle to the $n$th power, multiply by $\begin{pmatrix} B_0 & B_1 & B_2 & B_3 & B_4 \end{pmatrix}^T$ and look at the first entry in the resulting vector.
