插空法 大组合数取余
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
//求整数x和y,使得ax+by=d, 且|x|+|y|最小。其中d=gcd(a,b)
void gcd(LL a, LL b, LL& d, LL& x, LL& y)
{
if(!b)
{
d = a;
x = 1;
y = 0;
}
else
{
gcd(b, a%b, d, y, x);
y -= x * (a/b);
}
}
//计算模n下a的逆。如果不存在逆, 返回-1
LL inv(LL a, LL n)
{
LL d, x, y;
gcd(a, n, d, x, y);
return d == 1 ? (x+n)%n : -1;
}
LL cm(LL n, LL m, LL p)
{
LL ans1 = 1, ans2 = 1;
while(m)
{
ans1 = ans1*n%p;
ans2 = ans2*m%p;
n--;
m--;
}
return ans1*inv(ans2, p)%p;
}
LL lucas(LL n, LL m, LL p)
{
if(m == 0)
return 1;
return lucas(n/p, m/p, p)*cm(n%p, m%p, p)%p;
}
int main()
{
LL n, m, p;
while(scanf("%lld %lld %lld", &n, &m, &p) != EOF)
{
printf("%lld\n", lucas(n-2*m+1+m, m, p));
}
return 0;
}