#1616. 二项式系数

二项式系数

题目描述

这是一道模板题。

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

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

输入格式

第一行两个正整数 TTMM 表示有 TT 组询问和模数 MM

第二行至第 T+1T+1 行每行两个整数 nnmm 表示询问。

输出格式

对于每一组询问,输出 (nm)modM\binom{n}{m}\bmod M

样例

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

80728
45444
1
93000
49290

数据范围与提示

M=ipiei<109M=\prod_i p_i^{e_i}\lt 10^9 其中 i\forall ipip_i 为素数且 eie_i 为正整数,ij\forall i\neq jpipjp_i\neq p_jipiei106\sum_i p_i^{e_i}\leq 10^6

0<T2×1050\lt T\leq 2\times 10^50mn10180\leq m\leq n\leq 10^{18}