记录编号	323943	评测结果	AAAAAAAAAA
题目名称	[福建2011Day2] 组合数	最终得分	100
用户昵称	森林	是否通过	通过
代码语言	C++	运行时间	0.001 s
提交时间	2016-10-17 15:45:48	内存使用	1.05 MiB

#include <cstdio>
#include<stdlib.h>
#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[MOD+10];
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||m==n-1)return n;
	ull a=1;
	for(ull i=1;i<=m;i++)a=((a%MOD*(n-i+1)%MOD*N[i])+MOD)%MOD;
	return a%MOD;
}
inline ull lucas(ull n,ull m){
	if(m==0||n==m)return 1;
	if(m==1||m==n-1)return n;
	return C(n%MOD,m%MOD)%MOD*lucas(n/MOD,m/MOD)%MOD;
}
inline ull qpow(ull a,ull x){
	ull res=1;
	for(;x;x>>=1,a=a*a%MOD)if(x&1)res=res*a%MOD;
	return res;
}
int main(){
    freopen("com.in","r",stdin);
	freopen("com.out","w",stdout);
	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)%MOD);
	return 0;
}