#10228. 「一本通 6.6 例 3」组合

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 1bentong

题目描述

给出组合数 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 的结果。

样例

样例输入

2
5 2 3
5 2 61

样例输出

1
10

数据范围与提示

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