记录编号	132343	评测结果	AAAAAAAAAA
题目名称	[HNOI 2008] 越狱	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	0.019 s
提交时间	2014-10-25 19:58:08	内存使用	0.28 MiB

#include<cstdio>
#include<iostream>
using namespace std;
long long n,m,zj1,zj2,zj3,zj4=1,zj5=1;
int main()
{
	freopen("prisona.in","r",stdin);
	freopen("prisona.out","w",stdout);
	scanf("%lld%lld",&m,&n);
	m%=100003;zj1=m;zj2=n;zj3=m;
	while(n)
	{
		if(n&1){zj4*=zj3;zj4%=100003;}
		zj3*=zj3;
		zj3%=100003;
		n>>=1;
	}
	n=zj2-1;
	zj3=m-1;
	while(n)
	{
		if(n&1){zj5*=zj3;zj5%=100003;}
		zj3*=zj3;
		zj3%=100003;
		n>>=1;
	}
	zj5*=zj1;
	zj5%=100003;
	zj4-=zj5;
	zj4%=100003;
	if(zj4<0)zj4+=100003;
	printf("%lld\n",zj4);
	return 0;
}