记录编号	284256	评测结果	AAAAAAAAAA
题目名称	1040.[福建2011Day2] 组合数	最终得分	100
用户昵称	森林	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-07-17 16:29:40	内存使用	0.30 MiB

#include <cstdio>
#define JW fclose(stdin); fclose(stdout);
#define WJ(name) freopen(#name".in","r",stdin);freopen(#name".out","w",stdout);
typedef unsigned long long ull;
using namespace std;
const ull MOD=100003;
ull n,m,N[1010];
inline void QR(ull& x){
	char ch;
	while(ch=getchar(),ch<'0'||ch>'9');
	x=ch-48;
	while(ch=getchar(),ch>='0'&&ch<='9')x=x*10+ch-48;
}
inline void QW(ull _num){
	ull __cnt=0;
	char _str[100];
	while(_str[++__cnt]=_num%10+'0',_num/=10);
	while(putchar(_str[__cnt]),--__cnt);
}
inline ull C(ull n,ull m){
	if(m==0||n==m)return 1;
	if(m==1)return n;
	ull a=1;
	for(ull i=n-m+1;i<=n;i++)a*=i,a%=MOD;
	for(ull i=2;i<=m;i++)a*=N[i],a%=MOD;
	return a%MOD;
}
inline ull lucas(int n,int m){
	if(m==0||n==m)return 1;
	if(m==1)return n;
	return C(n%MOD,m%MOD)%MOD*lucas(n/MOD,m/MOD)%MOD;
}
int main(){
	WJ(com);
	QR(n),QR(m);
	N[1]=1;
	for(ull i=2;i<=m;i++)N[i]=(MOD-MOD/i)*N[MOD%i]%MOD;
	QW(lucas(n,m));
	JW;
	return 0;
}