bzoj 1008: [HNOI2008]越狱

/**************************************************************
    Problem: 1008
    User: lxy8584099
    Language: C++
    Result: Accepted
    Time:4 ms
    Memory:820 kb
****************************************************************/
 
/*
    可能发生的方案数 = 总方案数 - 不可能发生的方案数
                     = n^m - m*(m-1)^(n-1) 
*/
 
#include<cstdio>
#define ll long long
using namespace std;
const int MOD=100003;
ll ksm(ll a,ll b,ll p)
{
    ll res=1;
    for(;b;b>>=1,(a*=a)%=p) if(b&1) (res*=a)%=p;
    return res;
}
int main()
{
    ll n,m;scanf("%lld%lld",&m,&n);
    ll res=ksm(m,n,MOD);
    res=res-(m*ksm(m-1,n-1,MOD))%MOD;
    res=(res%MOD+MOD)%MOD;
    printf("%lld\n",res);
    return 0;
}