8860: [yosupo] Enumerative Combinatorics - Binomial Coefficient
[Creator : ]
Description
Given integers $n,k$ and $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 200,000$
- $1 \leq m \leq 10^6$
- $0 \leq k \leq n \leq 10^{18}$
- $1 \leq m \leq 10^6$
- $0 \leq k \leq n \leq 10^{18}$
Sample 1 Input
3 10007
4 2
0 0
1000000007 998244353
Sample 1 Output
6
1
0
Sample 2 Input
11 60
20 0
20 1
20 2
20 3
20 4
20 5
20 6
20 7
20 8
20 9
20 10
Sample 2 Output
1
20
10
0
45
24
0
0
30
20
16