学步园

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 11
5 2 11

Sample Output

5
6

利用插板法：

先把数字排列一下，然后咱们是要求的m个数字，那么也就是把m个数字插入n-m中间，岂不是不相邻了么？？？

n-m个空，当然可以产生n-m+1个位置，则方法数目就是C（n - m + 1，m），剩下的，%P（P是一个素数），当然就是lucas了。。

还有一点需要注意那就是，P太大，预处理爆内存，所以只能够边除边乘，及从 n - m + i/ i ---循环n次,

贴出代码:

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <string>

using namespace std;

int N, M, P;


/*
void init()
{
	fac[0] = 1;
	for (int i = 1; i <= P; i++)
	{
		fac[i] = (long long int) fac[i - 1] * i % P;
	}
}
*/
//因为P太大了,就不能提起预处理了,
 
int quick_pow(int a, int n)
{
	int ans = 1;
	while (n)
	{
		if (n & 1)
		{
			ans = (long long int)ans * a % P;
		}
		a = (long long int) a * a % P;
		n >>= 1;
	}
	return ans;
}


int C(int n, int m)
{
	if (n < m)
	{
		return 0;
	}
	long long int ans = 1;
	int a;
	int b;
	for (int i = 1; i <= m; i++)
	{
		a = (n - m + i) % P;
		b = i % P;
		ans = ans * ((long long int)a * quick_pow(b, P - 2) % P) % P;
	}
	return ans % P;
}

int lucas(int n, int m)
{
	if (m == 0)
	{
		return 1;
	}
	return (long long int)C(n % P, m % P) * lucas(n / P, m / P) % P;
}

int main()
{
	while (scanf("%d%d%d", &N, &M, &P) != EOF)
	{
//		init();
		int t = N - M + 1;
		if (t < M)
		{
			printf("0\n");
			continue;
		}
		if (M > t / 2)
		{
			M = t - M;
		}
		int ans = lucas(t, M);
		printf("%d\n", ans);
	}
//	system("pause");
	return 0;
}