题目描述

给出组合数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

备注

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