二项式系数（Binomial Coefficient）

问题描述

给定整数 $n, k, m$，计算二项式系数

约束条件

• $1 \leq T \leq 2 \times 10^5$
• $1 \leq m \leq 10^6$
• $0 \leq k \leq n \leq 10^{18}$

输入格式

$T\ m$
$n_0\ k_0$
$n_1\ k_1$
:
$n_{T-1}\ k_{T-1}$

输出格式

对每组输入，输出一行：$\binom{n_i}{k_i} \bmod m$

3 10007
4 2
0 0
1000000007 998244353

6
1
0

11 60
20 0
20 1
20 2
20 3
20 4
20 5
20 6
20 7
20 8
20 9
20 10

1
20
10
0
45
24
0
0
30
20
16