181 二项式系数

这是一道模板题。

求二项式系数 $\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$。

$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}$。