题目描述

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

输入格式

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

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

输出格式

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

样例

输入样例

2
5 2 3
5 2 61

输出样例

1
10

数据范围与提示

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