考虑越狱的情况有些复杂，不如考虑总情况减去不越狱的情况。
显然，总情况为 $m^n$ 种，不越狱的情况为 $m*(m-1)*(m-1)*(m-1)....$ 即为 $m*(m-1)^(n-1)$.
做差即可。
Code:
#include<cstdio>
#include<iostream>
typedef long long ll;
using namespace std;
const ll mod=100003;
ll pow(ll a,ll b,ll c){
ll res=1;
while(b>0){
if(b&1) res=(res*a)%c;
a=(a*a) % c;
b>>=1;
}
return res % c;
}
int main(){
ll n,m;
cin>>m>>n;
cout<<(pow(m,n,mod)-(pow(m-1,n-1,mod)*(m%mod))%mod+mod)%mod;
return 0;
}
原文：https://www.cnblogs.com/guangheli/p/9872412.html