BZOJ 1008:[HNOI2008]越狱

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
typedef long long LL;
using namespace std;
const LL mod=100003;
LL n,m,ans,tp;
LL ksm(LL a,LL b) {
    LL base=a,res=1;
    while(b) {
        if(b&1) (res*=base)%=mod;
        (base*=base)%=mod;
        b>>=1;
    }
    return res;
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    scanf("%lld%lld",&m,&n);
    ans=ksm(m,n);
    tp=(m*ksm(m-1,n-1))%mod;
    ((ans-=tp)+=mod)%=mod;
    printf("%lld\n",ans);
    return 0;
}