监狱有连续编号为1...N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果

相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱

　　输入两个整数M，N.1<=M<=10^8,1<=N<=10^12

　　可能越狱的状态数，模100003取余

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

/*ll quickpower(ll m,ll n)//简写版本

{

    if(n==0) return 1;

    ll temp=quickpower(m,n>>1);// n>>1 == n/2  n的二进制右移几位就是除以2的n次方

    temp=temp*temp%100003;

    if(n&1) temp=temp*m%100003;// n&1也就是取n的二进制最低位，判断n是否为奇数，是则为1

    return temp%100003;

}*/

ll quickpower(ll m,ll n)//更容易看懂的版本

{

    if(n==0) return 1;

    else

    {

        while((n&1)==0)

        {

            n>>=1;

            m=m*m%100003;

        }

    }

    int temp=m;

    n>>=1;

    while(n!=0)

    {

        m=m*m%100003;

        if((n&1)!=0)    temp=temp*m%100003;

        n>>=1;

    }

    return temp;

 }

int main()

{

    ll m,n;

    cin>>m>>n;

    m%=100003;

    ll ans=quickpower(m,n);

    ans-=(m*quickpower(m-1,n-1))%100003;

    cout<<(ans+100003)%100003<<endl;

    return 0;

 }