题目描述

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

输入格式

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

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

输出格式

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

2
5 2 3
5 2 61

1
10

提示

对于所有数据，T≤100，1≤m≤n≤${10}^9$，m≤${10}^4$，m<p<${10}^9$，p是素数。