本题可以采用容斥原理补集的思想。

考虑 $\mathrm{n}$ 个犯人，$\mathrm{m} $种宗教，如何安排不会导致犯罪。

第一个位置可以有 $\mathrm{m}$ 个选择，则与第一个相邻的第二个位置就只有 $\mathrm{m-1}$ 中选择。

考虑第 $\mathrm{i}$ 个位置，则为了不和他左侧的 $\mathrm{i-1}$ 位置发生冲突，一共有 $\mathrm{m-1}$ 种选择。

因此不会导致犯罪的方案是: $\mathrm{m \cdot (m - 1)^{n-1}}$

则会导致犯罪的方案是：$\mathrm{m^n - m \cdot (m - 1)^{n-1}}$

#include <iostream>

using namespace std;

typedef long long LL;

const int mod = 100003;

int qmi(int a, LL b) {
    int res = 1;
    while (b) {
        if (b & 1) res = (LL) res * a % mod;
        a = (LL) a * a % mod;
        b >>= 1;
    }
    return res;
}

int main() {
    int m;
    LL n;
    scanf("%d%lld", &m, &n);

    int res = (qmi(m, n) - (LL)m * qmi(m - 1, n - 1) % mod + mod) % mod;
    printf("%d\n", res);

    return 0;
}