记录编号	134403	评测结果	AAAAAAAAAA
题目名称	[HNOI 2008] 越狱	最终得分	100
用户昵称	乌龙猹	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2014-10-30 06:31:04	内存使用	0.29 MiB

#include<cstdio>
#include<cctype>
#define Mod 100003
using namespace std;

long long ret;
char ch;
long long qin()
{
	ret=0;
	while(ch=getchar(),!isdigit(ch));
	while(ret=ret*10+ch-'0',ch=getchar(),isdigit(ch));
	return ret;
}

long long n,m;

long long qpow(long long a,long long b)
{
	long long Ans=1;
	while(b)
	{
		if(b&1)
		{
			Ans*=a;
			Ans%=Mod;
		}
		a*=a;
		a%=Mod;
		b>>=1;
	}
	return Ans;
}

int main()
{
    freopen("prisona.in","r",stdin);
	freopen("prisona.out","w",stdout);
	m=qin();n=qin();
	long long ans=(qpow(m,n)-qpow(m-1,n-1)*m)%Mod;
	if(ans<0) ans+=Mod;
	printf("%lld\n",ans);
	return 0;
}