Stirling numbers via modular arithmetic

Base cases. $\left\{{n\atop 1}\right\}=1$, $\left\{{n\atop n}\right\}=1$, $\left\{{n\atop k}\right\}=0$ if $k>n$ or $k=0$ (for $n>0$).

Recursion. Partition the set $\{1,\ldots,n\}$ into $k$ blocks. If element $n$ is alone: $\left\{{n-1\atop k-1}\right\}$ ways. Otherwise, $n$ joins one of the $k$ blocks of a partition of the first $n-1$ elements into $k$ blocks: $k\cdot\left\{{n-1\atop k}\right\}$ ways.

Values.
- $\left\{{3\atop 2}\right\}=3$
- $\left\{{4\atop 2}\right\}=7$
- $\left\{{4\atop 3}\right\}=6$

Conclusion. The recursion holds.