题目描述

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

示例1

输入

2
5 2 3
5 2 61

输出

1
10

备注

输入样例 #2

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

输出样例 #2

0
324387113
15
0
42172419

输入样例 #3

5
330300154 52 193
170413171 3237 469762049
964346147 5745 23068673
172814610 140 257
302494824 2788 167772161

输出样例 #3

53
56170734
14070372
0
41371293

数据范围

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