我们先考虑第一个囚犯，它有$m$种可能。
接下来，如果下一个囚犯的宗教信仰与他前一个的不同，那么就有$m-1$种可能。
而如果相同，就只有$1$种可能。此时，余下没有考虑的囚犯，每人都有$m$种可能，并且此时可能发生越狱。
那么答案就是$s=\sum_{i=1}^{n-1} m^i(m-1)^{n-i-1}$
而$x^n-y^n=(x-y)\left(x^{n-1}+x^{n-2}y+x^{n-3}y^2+\dots+xy^{n-2}+y^{n-1}\right)$
$\therefore s+(m-1)^{n-1}=\cfrac{m^n-(m-1)^n}{m-(m-1)}=m^n-(m-1)^n$
$s=m^n-(m-1)^n-(m-1)^{n-1}$,再快速幂即可。
(求出不会越狱的方案数，再用总方案数减去也可。我只是开拓一下思维)
Code:

#include<iostream>
#include<cstdio>
using namespace std;
#define MOD 100003
int mult(long long x,long long y)//指数和底数
{
    if(x==0)return 1;
    if(x==1)return y%MOD;
    long long ret=mult(x/2,y);
    ret=ret*ret%MOD;
    if(x%2)ret*=y,ret%=MOD;
    return (int)(ret);
}//快速幂
int main()
{
    long long n,m;
    cin>>m>>n;
    m%=MOD;
    int ans;
    ans=((mult(n,m)-mult(n,m-1)-mult(n-1,m-1))%MOD+MOD)%MOD;
    cout<<ans<<endl;
    return 0;
}