11332: [yosupo] Enumerative Combinatorics - Binomial Coefficient (Prime Mod)
[Creator : ]
Description
Given integers $n,k$ and a prime $m$, print $\binom{n}{k} \bmod m$.
Each test consists of $T$ cases, and $m$ is fixed in all cases.
Each test consists of $T$ cases, and $m$ is fixed in all cases.
Input
$T\ m$
$n_0\ k_0$
$n_1\ k_1$
$\vdots$
$n_{T-1}\ k_{T-1}$
$n_0\ k_0$
$n_1\ k_1$
$\vdots$
$n_{T-1}\ k_{T-1}$
Output
For each line, print $\binom{n}{k} \bmod m$.
Constraints
- $1 \leq T \leq 10^6$
- $1 \leq m \leq 2^{30}$
- $m$ is a prime
- $0 \leq n, k \lt \min(m, 10^7)$
- $1 \leq m \leq 2^{30}$
- $m$ is a prime
- $0 \leq n, k \lt \min(m, 10^7)$
Sample 1 Input
3 10007
4 2
5 4
100 50
Sample 1 Output
6
5
9219
Sample 2 Input
4 2
0 0
0 1
1 1
1 0
Sample 2 Output
1
0
1
1