题目描述

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

限制与提示

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