Description
　　监狱有连续编号为1…N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果
相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱
Input
　　输入两个整数M，N.1<=M<=108,1<=N<=1012
Output
　　可能越狱的状态数，模100003取余
Sample Input
2 3
Sample Output
6
HINT
　　6种状态为(000)(001)(011)(100)(110)(111)

容斥问题？ n n n个房间 m m m种宗教，所有可能情况就是 m n m^n mn种，然后再减去不可能越狱的情况，也就是两个相邻的房间是不同的宗教，所以上一个房间有 m m m种选择，下一个房间就只有 m − 1 m-1 m−1，那也就是除了第一个房间，后面 n − 1 n-1 n−1个房间都是 m − 1 m-1 m−1种选择，那么答案就是 m n − m ∗ ( m − 1 ) n − 1 m^n-m*(m-1)^{n-1} mn−m∗(m−1)n−1，快速幂，然后注意中间乘的时候可能爆ll，所以乘之前都取一下模比较好，然后还有一个最后结果可能是负数（本来答案是不会，但是取模后相减就有可能出现负数了）

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD=100003;
ll m,n;
ll pow_mod(ll x,ll n){
   
    ll ans=1;
    while(n){
   
        if(n%2){
   
            ans=(ans%MOD*x%MOD)%MOD;
        }
        x=(x%MOD*x%MOD)%MOD;
        n>>=1;
    }
    return ans%MOD;
}
int main(void){
   
    scanf("%lld%lld",&m,&n);
    ll ans=pow_mod(m,n)%MOD-m*(pow_mod(m-1,n-1)%MOD)%MOD;
    //取模再相减可能出现负数！
    printf("%lld\n",ans>0?ans:ans+MOD);
    return 0;
}