Kombinační číslo modulo m

Kombinační čísla modulo \(m\) vytváří hezké fraktály. Pojďme vymyslet algoritmus, který pro dané \(n\), \(k\) a \(m\) spočítá \({n\choose k}\bmod m\).

Předpokládejte přitom, že \(n\) a \(k\) jsou obvykle mnohem větší než \(m\).

V základní verzi úlohy předpokládejte, že \(m\) je prvočíslo, až 5 dalších bodů můžete dostat za řešení pro obecné \(m\).