# description

```
There is a very big garden at Raven’s residence. We regard the garden as an n*m rectangle. Raven’s house is at the top left corner, and the exit of the garden is at the bottom right. He can choose to take one step to only one direction (up, down, left or right) each time. Raven wants to go out of the garden as quickly as possible, so he wonders how many routes he could choose.
Raven knows there are many possible routes, so he only wants to know the number, which is the result that the total number of possible routes modes a given value p. He knows it is a simple question, so he hopes you may help him to solve it.

```

# input

```
The first line of the input contains an integer T, which indicates the number of test cases.
Then it is followed by three positive integers n, m and p (1 &lt;= n, m, p &lt;= 10^5), showing the length and width of the garden and p to be the mod of the result.

```

# output

```
For each case, output one number to show the result (the sum modes p).
```

```
3
2 2 5
2 6 16
6 6 24

```

```
2
6
12

```

# hint

```
Sample 1: There are 2 routes in total.
Sample 2: There are 6 routes in total.
Sample 3: There are 252 routes in total.

```

```#include <iostream>
#include <stdio.h>
#include <string>
#include <string.h>
#include <algorithm>
const int N=1e5+100;
using namespace std;
typedef long long ll;

int n,m,p,ct;
ll prime[2*N];
bool isprime[2*N];
int t[5][2*N];

void solve()
{
ct=0;
memset(isprime,false,sizeof(isprime));
isprime[0]=isprime[1]=true;
for(int i=2;i<=200100;i++)
{
if(!isprime[i])
{
prime[++ct]=i;
for(int j=i+i;j<=200100;j+=i)
isprime[j]=true;
}
}
}

int cal(int x,int pos)
{
int i=1;
for(;i<=ct&&prime[i]<=x;i++)
{
int ans=0,tmp=prime[i];
while(x/tmp!=0)
{
ans+=x/tmp;
tmp*=prime[i];
}
t[pos][i]=ans;
}
return i;
}

ll quick(ll a,int b )
{
ll ans=1;
while(b)
{
if(b&1)ans=ans*a%p;
b=b/2;
a=a*a%p;
}
return ans;
}

int main()
{
int T;
scanf("%d",&T);
solve();
while(T--)
{
scanf("%d%d%d",&n,&m,&p);
memset(t,0,sizeof(t));

if(n-1==0)
{
printf("1\n");
continue;
}
if(n-1==1)
{
printf("%d\n",(n+m-2)%p);
continue;
}

int t1=cal(n+m-2,1);
int t2=cal(n-1,2);
int t3=cal(m-1,3);
int cnt=max(t1,max(t2,t3));

for(int i=1;i<cnt;i++)
{
t[1][i]=t[1][i]-t[2][i]-t[3][i];
}

ll ans=1;
for(int i=1;i<cnt;i++)
{
ans=ans*quick(prime[i],t[1][i])%p;
}
printf("%lld\n",ans);

}
return 0;
}
```

## 大组合数取模之lucas定理模板,1&lt;=n&lt;=m&lt;=1e9,1&lt;p&lt;=1e6，p必须为素数

typedef long long ll; /********************************** 大组合数取模之lucas定理模板,1<=n<=m<=1e9,1<p<=1e6,p必须为素数 输入:C(n,m)%p 调用lucas(n,m,p) 复杂度:min(m,p)*log(m) ***********************************/ //ax + by = gcd(a,b) //传入固定值a,b.放回 d=gcd(a,b), x , y

## 大组合数取模

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1119 考虑从(1,1)->(n,m)必定会向下走n-1步,向右走m-1步,那么总的走法是C(n-1+m-1,m-1). 关于组合数取模:大神博客:http://blog.csdn.net/acdreamers/article/details/8037918 1 #include <iostream> 2 #include <string.h> 3 #

## 排列组合+组合数取模 HDU 5894

1 // 排列组合+组合数取模 HDU 5894 2 // 题意:n个座位不同,m个人去坐(人是一样的),每个人之间至少相隔k个座位问方案数 3 // 思路: 4 // 定好m个人 相邻人之间k个座位 剩下就剩n-(m+1)*k个座位 5 // 剩下座位去插m个不同的盒子==就等价n个相同的球放m个不同的盒子 6 // 然后组合数出来了 7 // 乘n的话是枚举座位,除m是去掉枚举第一个座位的时候,剩下人相邻的座位相对不变的情况 8 9 #include <iostream> 10 #incl