题目描述

给出组合数 $C(n,m)$ 表示从 $n$ 个元素中选出 $m$ 个元素的方案数。例如 $C(5,2) = 10, C(4,2) = 6$。可是当 $n,m$ 比较大的时候，$C(n,m)$ 很大。于是 xiaobo 希望你输出 $C(n,m) \bmod p$ 的值。

输入格式

输入数据第一行是一个正整数 $T$，表示数据组数；

接下来是 $T$ 组数据，每组数据有 $3$ 个正整数 $n,m,p$。

输出格式

对于每组数据，输出一个正整数，表示 $C(n,m) \bmod p$ 的结果。

样例

5
181168415 147 193
261739313 7560 469762049
24444686 2 17
195153914 58 97
212311573 3829 104857601

0
324387113
15
0
42172419

数据范围与提示

对于所有数据，$T\le 100$，$1\le m\le n\le 10^9$，$m\le 10^4$，$m\lt p\lt 10^9$，$p$ 是素数。

来源

一本通 6.6 例 3