题目描述

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

输入样例

2
5 2 3
5 2 61

输出样例

1
10

提示

数据范围与提示： 对于所有数据，1≤m≤n≤10^9 ，m≤10^4 ，m < p <10^9 ，$p$ 是素数。

评测数据说明

本题使用经输入域与独立答案完整核验的第三方公开训练数据，并补充自编边界及公开样例，共10个测试点，非原站或官方原始数据。总分100分。公开训练数据来自HEEKDragonOne/ACM固定提交，逐点来源与SHA256保存在教师复核材料。