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

「一本通 6.6 例 3」组合

题目描述

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

输入

输入数据第一行是一个正整数 TT,表示数据组数;

接下来是 TT 组数据,每组数据有 33 个正整数 n,m,pn,m,p

输出

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

样例

2
5 2 3
5 2 61
1
10

提示

数据范围与提示:

对于所有数据,1mn109m104m<p<1091≤m≤n≤10^9 ,m≤10^4 ,m < p <10^9pp 是素数。

来源

一本通在线评测