#181. 二项式系数

标签: 传统 | 时间限制: 2000 ms | 内存限制: 256 MiB 通过: 48 | 提交: 131

题目描述

这是一道模板题。

求二项式系数 $\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} < 10^9$ 其中 $\forall i$ 有 $p_i$ 为素数且 $e_i$ 为正整数， $\forall i \neq j$ 有 $p_i \neq p_j$ ， $\sum_i p_i^{e_i} \le 10^6$ 。

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