Given a set S = {1, 2, ..., n}, number m and p, your job is to count how many set T satisfies the following condition:

• T is a subset of S
• |T| = m
• T does not contain continuous numbers, that is to say x and x+1 can not both in T

Input

There are multiple cases, each contains 3 integers n ( 1 <= n <= 10⁹ ), m ( 0 <= m <= 10⁴, m <= n ) and p ( p is prime, 1 <= p <= 10⁹ ) in one line seperated by a single space, proceed to the end of file.

Output

Output the total number mod p.

Sample Input

5 1 115 2 11

Sample Output

56

题目大意：

给一个集合，一共n个元素，从中选取m个元素，满足选出的元素中没有相邻的元素，一共有多少种选法(结果对p取模1 <= p <= 10^9) 

思路：
好像是裸题、、、、

用插板法求出组合数。既然是从n个数中选择m个数，那么剩下的数为n-m，那么可以产生n-m+1个空，这道题就变成了把m个数插到这n-m+1个空中有多少种方法，即C(n-m+1,m)%p

但是求乘法逆元的已经行不通了，因为这里我们不确定他给出的p是否为素数，这样我们就只能用卢卡斯定理了
卢卡斯定理不会的转：http://www.cnblogs.com/L-Memory/p/7352397.html
不要预处理了，因为我们这里p不知道，而且如果要处理的话就要开10^9*long long空间。
代码：

#include<cstdio>#include<cstring>#include<cstdlib>#include<iostream>#include<algorithm>#define ll long long using namespace std;ll t,n,m,p,ans;ll read(){    ll x=0,f=1; char ch=getchar();    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1; ch=getchar();}    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘; ch=getchar();}    return x*f;}ll qpow(ll n,ll k,ll q){    ll res=1;    while(k)    {        if(k&1) res=res*n%p;         n=n*n%p; k>>=1;    }return res;}ll c(ll n,ll m,ll p){    ll n1=1,m1=1;    if(m>n) return 0;    for(int i=1;i<=m;i++)     m1=m1*i%p;    for(int i=n-m+1;i<=n;i++)     n1=n1*i%p;    return n1*qpow(m1,p-2,p)%p; }ll lus(ll n,ll m,ll p){    if(m==0) return 1;    return c(n%p,m%p,p)*lus(n/p,m/p,p)%p;}int main(){    while(scanf("%lld%lld%lld",&n,&m,&p)!=EOF)    {        ans=lus(n-m+1,m,p);        printf("%lld\n",ans);    }    return 0;}

zoj——3557 How Many Sets II