题目描述

这是一道模板题。

求二项式系数 $\binom{n}{m}\bmod M$，每个测试点有多组询问但模数固定。其中

$$\binom{n}{m}=\frac{n!}{m!(n-m)!}$$

输入格式

第一行两个正整数 $T$ 和 $M$ 表示有 $T$ 组询问和模数 $M$。

第二行至第 $T+1$ 行每行两个整数 $n$ 和 $m$ 表示询问。

输出格式

对于每一组询问，输出 $\binom{n}{m}\bmod M$。

样例

5 114514
58 4
88 42
13 13
98 29
100 18

80728
45444
1
93000
49290

数据范围与提示

$M=\prod_i p_i^{e_i}\lt 10^9$ 其中 $\forall i$ 有 $p_i$ 为素数且 $e_i$ 为正整数，$\forall i\neq j$ 有 $p_i\neq p_j$，$\sum_i p_i^{e_i}\leq 10^6$。

$0\lt T\leq 2\times 10^5$ 且 $0\leq m\leq n\leq 10^{18}$。