传送门 ↬\looparrowright

Problem Description

Although winter is far away, squirrels have to work day and night to save beans. They need plenty of food to get through those long cold days. After some time the squirrel family thinks that they have to solve a problem. They suppose that they will save beans in nn different trees. However, since the food is not sufficient nowadays, they will get no more than mm beans. They want to know that how many ways there are to save no more than mm beans (they are the same) in nn trees.
Now they turn to you for help, you should give them the answer. The result may be extremely huge; you should output the result modulo pp, because squirrels can’t recognize large numbers.

Input

The first line contains one integer TT, means the number of cases.
Then followed TT lines, each line contains three integers n,m,pn, m, p, means that squirrels will save no more than mm same beans in nn different trees, 1≤n,m1 \le n, m≤1000000000\le 1000000000, 1<p<1000001 < p < 100000 and pp is guaranteed to be a prime.

Output

You should output the answer modulo pp.

Sample Input

2
1 2 5
2 1 5

Sample Output

3
3

Hint

For sample 11, squirrels will put no more than 22 beans in one tree. Since trees are different, we can label them as 1,2,⋯1, 2,\cdots and so on.
The 33 ways are: put no beans, put 11 bean in tree 11 and put 22 beans in tree 11. For sample 22, the 33 ways are: put no beans, put 11 bean in tree 11 and put 11 bean in tree 22.

Translation

有 nn 棵松树，每棵树上的松果都足够多，我们需要采不多于 mm 颗松果，问有多少种取法。每颗松果都是相同的，nn 棵树是不同的。答案对质数 pp 取模。

Idea

设一共采 kk 颗松果，0≤k≤m0\le k\le m 且 k∈Nk\in \mathrm N；第 ii 棵树上采 aia_i 颗松果，ai∈Na_i\in \mathrm N，那么有 ∑i=1nai=k\sum\limits_{i=1}^n a_i=k。相当于将 kk 个相同的球放入 nn 个不同箱子且允许有空箱子。
先考察将 kk 个相同的球放入 nn 个不同箱子且不允许有空箱子的情况。可利用插板法，要将 kk 个相同分成 nn 份，就要在 kk 个球的 k−1k-1 个空隙中插入 n−1n-1 块隔板。因此，答案为 Ck−1n−1C_{k-1}^{n-1}。
如果给每个箱子一个球，就可以把问题转化为不能空的情况了。问题等价于将 n+kn+k 个相同的球放入 nn 个不同的箱子且不允许空箱子。因此，将 kk 个相同的球放入 nn 个不同箱子且允许有空箱子的方法数为 Cn+k−1n−1C_{n+k-1}^{n-1}==Cn+k−1kC_{n+k-1}^{k}。
由于总共采的果子不超过 mm，即 k=0,1,⋯ ,mk=0,1,\cdots,m，所以不同的取法有 ∑k=0mCn+k−1k\sum\limits_{k=0}^m C_{n+k-1}^k 种。

$$ \begin{aligned}\sum\limits_{k=0}^m C_{n+k-1}^k&=C_{n-1}^0+C_{n}^1+C_{n+1}^2+\cdots+C_{n+m-1}^m\\&=C_n^0+C_{n}^1+C_{n+1}^2+\cdots+C_{n+m-1}^m\\&=C_{n+1}^1+C_{n+1}^2+\cdots+C_{n+m-1}^m\\&\quad\quad\quad\quad\quad\quad\quad\vdots\\&=C_{n+m-1}^{m-1}+C{n+m-1}^m\\&=C_{n+m}^m\end{aligned} $$

题目答案为 Cn+mm mod pC_{n+m}^m\bmod p。此处 n,mn,m 较大，且 pp 为质数，考虑使用卢卡斯定理。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
#include<cstdio>
#define N 100003
#define ll long long
using namespace std;
ll fac[N];//阶乘
//快速幂
ll qpow(ll a,ll b,int p)
{
	ll res=1;
	while(b)
	{
		if(b&1) res=res*a%p;
		a=a*a%p;
		b>>=1;
	}
	return res;
}
//预处理阶乘
inline void init(int p)
{
	fac[0]=1;
	int i;
	for(i=1;i<=p;i++) fac[i]=(fac[i-1]*i)%p;
}
//用逆元求组合数
inline ll C(int n,int m,int p)
{
	if(m>n) return 0;
	return fac[n]*qpow(fac[n-m],p-2,p)%p*qpow(fac[m],p-2,p)%p;
}
//卢卡斯定理递归求组合数取模
ll Lucas(int n,int m,int p)
{
	if(!m) return 1;
	return C(n%p,m%p,p)*Lucas(n/p,m/p,p)%p;
}
int main()
{
	int _;
	for(cin>>_;_;_--)
	{
		int n,m,p;
		scanf("%d%d%d",&n,&m,&p);
		init(p);
		printf("%lld\n",Lucas(n+m,n,p));
	}
	return 0;
}