当然本题只要分析出来公式，然后利用Lucas解都是浮云了。本题由于p很大，所以就不能阶乘预处理了。
题意是：给一个集合，一共n个元素，从中选取m个元素，满足选出的元素中没有相邻的元素，这样的选法一共有多少种？
本题正是利用隔板法：
一开头摆好m个球，然后向m+1个空位插球。中间任意一个空位不可为空。最后这m个的编号就是它是第几个球。
那么就先在m-1个空位上放球。再用普通隔板，n-2*m+1个球放m+1个位子，就是C(n-m+1,m)
#include <iostream>
long long n,m,p;
long long quick_mod(long long a,long long b)
{
long long ans=1;
a%=p;
while(b)
{
if(b&1)
{
ans=ans*a%p;
b--;
}
b>>=1;
a=a*a%p;
}
return ans;
}
long long C(long long n,long long m)
{
if(m>n)
return 0;
else
{
long long a,b,ans=1;
for(long long i=1;i<=m;i++)
{
a=(n+i-m)%p;
b=i%p;
ans=ans*(a*quick_mod(b,p-2)%p)%p;
}
return ans;
}
}
long long Lucas(long long n, long long m)
{
if(m==0) return 1;
else return (C(n%p,m%p)*Lucas(n/p,m/p))%p;
}
int main()
{
long long x,y;
while(std::cin>>x>>y>>p)
{
n=x-y+1;
m=y;
std::cout<<Lucas(n,m)<<std::endl;;
}
return 0;
}