此题主要是一个补集思想。

可能发生越狱的状态=所有状态-不会发生越狱的状态=M^N-M*(M-1)^(N-1)。

(M^N-M*(M-1)^(N-1))%P=(M^N%P-M*(M-1)^(N-1)%P+P)%P。

用快速幂来求解。

#include
     
      #define P 100003typedef long long ll;ll n,m;ll work(ll x,ll y){    ll now=x,ans=1;    for(;y;y>>=1,now=now*now%P)        if(y&1) ans=ans*now%P;    return ans;}int main(){    scanf("%lld%lld",&m,&n);    printf("%lld",(work(m%P,n)-m*work((m-1)%P,n-1)%P+P)%P);    return 0;}