二项式系数（质数模）

【题目描述】

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

每次测试包含 $T$ 组数据，且所有数据中 $m$ 均固定不变。

【输入】

第一行包含两个整数 $T$ 和 $m$。

接下来 $T$ 行，第 $i$ 行包含两个整数 $n_i\ k_i$。

【输出】

对每一行输出一个整数，表示 $\binom{n}{k} \bmod m$。

【输入样例】

3 10007
4 2
5 4
100 50

【输出样例】

6
5
9219

【输入样例2】

4 2
0 0
0 1
1 1
1 0

【输出样例2】

1
0
1
1

【数据范围】

• $1 \leq T \leq 1000000$
• $1 \leq m \leq 1073741824$
• $m$ 为质数
• $0 \leq n, k < \min(m, 10000000)$

【来源】

Library Checker（yosupo06） binomial_coefficient_prime_mod