难度： 黄

算法： 排列组合，快速幂

垃圾排列组合题。

不难得到答案为 $m^n-m\times (m-1)^{n-1}$，请读者自证。

使用快速幂求解即可。

注意快速幂和取模的规范性。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll m,n,mod=100003;
ll qp(ll a,ll b){
	ll ans=1,base=a;
	while(b){
		if(b%2) ans=(ans*base)%mod;
		base=base*base%mod;
		b/=2;
	}
	return ans;
}
int main(){
	scanf("%lld%lld",&m,&n);
	ll s1=qp(m,n);
	ll s2=((m%mod)*qp(m-1,n-1))%mod;
	printf("%lld",(s1-s2+mod)%mod);
}