记录编号	336323	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]寻找saber	最终得分	100
用户昵称	kito	是否通过	通过
代码语言	C++	运行时间	4.899 s
提交时间	2016-11-03 07:51:58	内存使用	160.42 MiB

#include<cstdio>
#include<ctime>
using namespace std;
#define fcl	fclose(stdin);	fclose(stdout);	return 0
	#define SUBMIT	2333
const int p=19999999;
int n,m,ans=0;
int Mu[30000010],Inv[30000010];
void ExGcd(int a,int b,int& x,int& y){
	if(b==0){
		x=1;	y=0;
		return;
	}
	ExGcd(b,a%b,x,y);
	int t=x;
	x=y;	y=t-(a/b)*y;
}

void Init(){
	Mu[0]=1;
	int x;
	if(p>n+m)	x=n+m;
	else	x=p-1;
	for(int i=1;i<=x;++i){
		Mu[i]=(Mu[i-1]*1ll*i)%p;
	}
	int y;
	ExGcd(Mu[x],p,Inv[x],y);
	Inv[x]%=p;	Inv[x]=(Inv[x]+p)%p;
	for(int i=x-1;i>=0;--i){
		Inv[i]=(Inv[i+1]*1ll*(i+1))%p;
	}
}

int C(int a,int b){
	if(b<0)	return 0;
	if(a<b)	return 0;
	int x=(Mu[a]*1ll*Inv[b])%p;
	x=(x*1ll*Inv[a-b])%p;
	return x;
}

int Lucas(int a,int b){
	if(b<0)	return 0;
	if(b==0)	return 1;
	return (Lucas(a/p,b/p)*1ll*C(a%p,b%p))%p;
}

int main(){
	#ifdef SUBMIT
	freopen("saber.in","r",stdin);
	freopen("saber.out","w",stdout);
	#endif
	scanf("%d%d",&n,&m);
	Init();
	ans=Lucas(n+m,m);
	ans=(ans-Lucas(n+m,m-2)+p)%p;
	printf("%d",ans);
	#ifndef SUBMIT
	getchar();	getchar();
	#endif
	fcl;
}