[HNOI2008] 越狱 快速幂

水。考虑不发生越狱的情况：即宗教相同的都不相邻，一号任意放\(m\)种宗教的人，此后\(n-1\)个房间都放与上一个宗教不同的人，有\(m-1\)种，所以共有\(m*(m-1)^{n-1}\)种。答案即\(m^n-m*(m-1)^{n-1}\)。快速幂即可。

注意，这里需要考虑模后相减为负的情况，此时将负值再加上模数变为正数即可。

#include 
    
     #define MOD 100003#define ll long longusing namespace std;ll m,n;ll qpow(ll x, ll k){    ll ans=1;    while(k){        if(k&1) ans=ans*x%MOD;        k>>=1;        x=x*x%MOD;    }    return ans;}int main(){    scanf("%lld %lld", &m, &n);    m%=MOD;    printf("%lld\n", (qpow(m, n)-qpow(m-1, n-1)*m%MOD+MOD)%MOD);    return 0;}