二项式系数

【题目描述】

给定整数 $n,k$ 和 $m$，输出 $\binom{n}{k} \bmod m$。

每组测试包含 $T$ 个询问，且所有询问中的 $m$ 固定不变。

【输入】

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

【输出】

每行输出一个 $\binom{n}{k} \bmod m$。

【输入样例】

3 10007
4 2
0 0
1000000007 998244353

【输出样例】

6
1
0

【输入样例2】

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

【输出样例2】

1
20
10
0
45
24
0
0
30
20
16

【数据范围】

• $1 \leq T \leq 200000$
• $1 \leq m \leq 1000000$
• $0 \leq k \leq n \leq 1000000000000000000$

【来源】

Library Checker（yosupo06） binomial_coefficient