二项式系数（质模）（Binomial Coefficient (Prime Mod)）

问题描述

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

约束条件

• $1 \leq T \leq 10^6$
• $1 \leq m \leq 2^{30}$，且 $m$ 为质数
• $0 \leq k \leq n < \min(m, 10^7)$

注：由于 $n < m$，可直接使用 预处理阶乘 + 费马小定理求逆元；若 $n \ge m$，则需 Lucas 定理，但本题约束 $n < m$，故无需 Lucas。

输入格式

$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
5 4
100 50

6
5
9219

4 2
0 0
0 1
1 1
1 0

1
0
1
1