P3197 [HNOI2008] 越狱 50分求调

源代码：

#include<bits/stdc++.h>
using namespace std;
long long n,m,mod=100003;
long long dfs(int x,int y){
	if(y==1){
		return x;
	}
	long long t=dfs(x,y/2);
	if(y%2==0){
		return (t*t)%mod;
	}
	else{
		return (t*t*x)%mod;
	}
}
int main(){
	cin>>m>>n;
	long long a=dfs(m,n)-(m%mod)*dfs(m-1,n-1)%mod;
	while(a<0){
		a+=mod;
	}
	a%=mod;
	cout<<a;
}