hdu3037Saving Beans

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2610    Accepted Submission(s): 966

2
1 2 5
2 1 5

3
3
Hint
Hint

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

#include<map>
#include<string>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<climits>
#include<list>
#include<iomanip>
#include<stack>
#include<set>
using namespace std;
typedef long long ll;
ll qpow(ll a,ll b,ll c)
{
	ll ans=1;
	while(b>0)
	{
		if(b&1)
			ans=ans*a%c;
		a=a*a%c;
		b>>=1;
	}
	return ans;
}
ll fac[100000];
ll fmt(ll a,ll b,ll c)
{
	return fac[a]*qpow(fac[b]*fac[a-b]%c,c-2,c)%c;
}
ll lucas(ll a,ll b,ll c)
{
	ll ans=1;
	while(a>0&&b>0)
	{
		if(a%c<b%c)
			return 0;
		ans=ans*fmt(a%c,b%c,c)%c;
		a/=c;
		b/=c;
	}
	return ans;
}
void create(ll a)
{
	fac[0]=1;
	for(ll i=1;i<a;i++)
		fac[i]=fac[i-1]*i%a;
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		ll n,m,p;
		cin>>n>>m>>p;
		create(p);
		cout<<lucas(n+m,m,p)<<endl;
	}
}