记录编号	576787	评测结果	AAAAAAAAAA
题目名称	[HNOI 2008] 越狱	最终得分	100
用户昵称	qyd	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2022-10-16 10:56:06	内存使用	0.00 MiB

#include<iostream>
using namespace std;
#define ll long long
ll qmimod(ll m,ll n);  //m^n;
const int mod=100003;
int main()
{
	freopen("prisona.in","r",stdin);
	freopen("prisona.out","w",stdout);
	
	ll m,n,ans;
	cin>>m>>n;
	m%=mod;
	
	ans=(qmimod(m,n)-m*qmimod(m-1,n-1))%mod;
	while(ans<0)
	  ans+=mod;
	  
	cout<<ans;
	
	return 0;
}
ll qmimod(ll m,ll n)
{
	m%=mod;
	
	if(n==1)
	  return m;
	else
	{
		ll base=qmimod(m,n/2)%mod;
		return ((n%2==0?1:m)*base*base)%mod;
	}
}