Предисловие: Задача нахождения числа сочетаний по простому модулю — баян. Но решение задачи с составным модулем я не нашел в интернете, поэтому написал тут свое решение, мб есть решения получше.

Задача: Дан модуль $$$M$$$. Необходимо ответить на запрос из двух чисел $$$N$$$ и $$$K$$$ посчитать число сочетаний из $$$N$$$ элементов по $$$K$$$ элементов (далее $$$C(N, K)$$$). Ответ нужно вывести по модулю $$$M$$$.

Решение: Для начала разложим $$$M$$$ на множители. Пусть $$$M={p_1}^{g_1} * ... * {p_t}^{g_t}$$$. Пусть мы знаем остаток $$$C(N, K)$$$ по каждому из модулей из списка: $$${p_1}^{g_1}, ... , {p_t}^{g_t}$$$. Тогда у нас появилась система из $$$t$$$ линейных сравнений вида $$$C(N, K)=r_i (mod$$$ $$${p_i}^{g_i})$$$. Степени различных простых чисел всегда взаимно простые, а значит можно применить китайскую теорему об остатках и найти остаток $$$C(N, K)$$$ по модулю произведения, а значит по исходному модулю.

Формула для КТО для двух сравнений: $$$C(N,K)=x_1 (mod$$$ $$$M_1)$$$, $$$C(N,K)=x_2 (mod$$$ $$$M_2)$$$ Равносильно $$$C(N,K)=(x_2-x_1)*inv(M_1, M_2)*M_1+x_1 (mod$$$ $$$M_1*M_2)$$$

Теперь осталось научиться находить остаток $$$C(N, K)$$$ по модулю степени простого $$$p^g$$$. По определению $$$C(N, K)=\frac{N!}{K!*(N-K)!}$$$, а значит необходимо научиться находить факториалы, умножать и делить по модулю степени простого. Но простое $$$p$$$ может быть меньше $$$K$$$ или $$$N-K$$$, тогда нам нужно будет разделить на $$$0$$$ по модулю, но, конечно для нуля нет обратного остатка, что вызывает проблему. Здесь можно использовать технику схожую с той, которую используют для нахождения факториала по простому модулю, меньшему $$$N$$$. Техника заключается в том, чтобы из каждого множителя факториала $$$(1, 2, 3, 4, 5, ..., N)$$$ убрать умножение на $$$p$$$, т.е. для любого $$$1<=i<=N$$$, разложить $$$i$$$ в произведение двух частей, одна из которых не делится на $$$p$$$, а другая соответственно является степенью $$$p$$$. Пусть $$$i=a_i*p^{b_i}$$$, тогда можно в "факториалы" записывать произведения $$$a_i$$$, вместо $$$i$$$. В пару с факториалом сохраним и сумму степеней $$$p$$$, т.е. Будем считать вести два массива $$$F[i]=\prod_{j=1}^{i}a_j$$$, $$$Nu[i]=\sum_{j=1}^{i}b_j$$$, тогда очевидно что $$$i!=F[i]*p^{Nu[i]}$$$. Такие массивы можно легко предподсчитать за $$$О(MAXN)$$$, где $$$MAXN$$$ — ограничение на максимальное значение $$$N$$$. Теперь мы можем посчитать $$$C(N, K)$$$ по модулю $$$p^g$$$, через эти два массива, $$$C(N, K) = \frac{N!}{K! * (N-K)!} = \frac{F[N] * p^{Nu[N]}}{F[K] * p^{Nu[K]} * F[N-K] * p^{Nu[N-K]}} = \frac{F[N]} {F[K] * F[N-K]} *$$$ $$$p^{Nu[N]-Nu[K]-Nu[N-K]}$$$. Т.к. $$$F[i]$$$ не содержит $$$p$$$, то оно взаимно просто с модулем $$$p^g$$$, а значит мы легко можем найти его обратное (можно даже предподсчитать обратные остатки для $$$F$$$). Пусть $$$rs=Nu[N]-Nu[K]-Nu[N-K]$$$, тогда если $$$rs >= g$$$, то остаток $$$p^{rs} = 0 (mod$$$ $$$p^g)$$$. Тогда можно предподсчитать для всех $$$0<=i<=g$$$, $$$Biv[i] = p^i (mod$$$ $$$p^g)$$$. Теперь мы можем посчитать $$$C(N, K) = \frac{F[N]}{F[K]*F[N-K]} * Biv[min(rs, g)] (mod$$$ $$$p^g)$$$. Если предподсчитать обратные факториалы, то получится $$$O(1)$$$ времени на запрос подсчета $$$C(N, K)$$$ по модулю $$$p^g$$$.

Сложность: На запрос числа сочетаний по модулю мы умеем отвечать за $$$O(1)$$$ на сам запрос и $$$O(MAXN * t + log(M) + sqrt(M))$$$ на предподсчет $$$F$$$ и $$$Nu$$$, $$$Biv$$$, разложения $$$M$$$ на простые, где $$$t$$$ — количество различных простых в разложении $$$M$$$. Тогда осталось лишь склеить все остатки с помощью формулы из первого абзаца решения. Формула для двух сравнений считается через деление по модулям $$${p_i}^{g_i}$$$, что можно делать с помощью теоремы Эйлера и бинарного возведения в степень за $$$O(log(\phi({p_i}^{g_i})))$$$, где $$$\phi$$$ — функция Эйлера, которую легко посчитать: $$$\phi({p_i}^{g_i})={p_i}^{g_i}-{p_i}^{g_i-1}$$$, что мы можем узнать за $$$O(1)$$$ т.к. степени мы предподсчитали, тогда получается на одно сливание необходимо $$$O(log({p_i}^{g_i}-{p_i}^{g_i-1})) = O(log({p_i}^{g_i}))$$$, что в сумме по всем $$$p_i$$$, равно $$$O(log({p_1}^{g_1}) + ... + log({p_t}^{g_t})) = O(log({p_1}^{g_1} * ... * {p_t}^{g_t})) = O(log(M))$$$. Также можно оценить количество простых в разложении $$$M$$$ ($$$t$$$) как $$$O(log(M))$$$. Тогда суммарная асимптотика получится, $$$O(log(M))$$$ на запрос и $$$O(MAXN*log(M)+sqrt(M))$$$ на предподсчет. Т.е. алгоритм эффективен в задачах при $$$M<10^{12}$$$, и $$$N<10^6$$$.