Число сочетаний по модулю простого числа

Даны n, k и простое число mod. Верните C(n, k) mod mod (число сочетаний из n по k). n может быть достаточно большим, чтобы считать треугольник Паскаля напрямую было накладно. Предпосчитайте факториалы по модулю mod и используйте малую теорему Ферма для обратных элементов: x^(mod-2) mod mod - это обратный к x элемент, когда mod простое.