# 思路
这道题可以从反面去考虑，即：先计算出不可能发生越狱的状态总数，并用它减去总状态数即为这道题要求的答案。
首先，在不失一般性的情况下，不妨设第一个房间里的犯人的宗教信仰为$p$，则第二个房间里的烦人的宗教信仰不能为$p$，因此第二个房间里的犯人的宗教信仰共有$(m - 1)$种可能性。同理，第三个房间里的犯人的宗教信仰也共有$(m - 1)$种可能性……故第二个到第$n$个房间里的烦人的宗教信仰共有$(n - 1)^{(m - 1)}$种可能性。而第一个房间里的犯人的信仰有$n$种可能，故不可能发生越狱的状态总数为
$$n×(n - 1)^{(m - 1)}$$
那么，总状态数是多少呢？容易求的总状态数为$n^m$，所以题目所求为
$$n^m-n×(n - 1)^{(m - 1)}$$
这道题还有一个要注意的地方：$m$最大为$10^8$，因此要用快速幂来计算
AC代码：
```cpp
#include<iostream>
using namespace std;
const long long MOD = 100003;
long long power(long long b, long long p) {
if(p == 0) {
return 1;
}
long long ans = power(b, p / 2);
ans = ans * ans % MOD;
if(p % 2 == 1) {
ans = ans * b % MOD;
}
return ans;
}
int main() {
long long m, n;
cin >> m >> n;
long long ans = ((power(m, n) - m * power(m - 1, n - 1)) % MOD + MOD) % MOD;
cout << ans << endl;
return 0;
}
```