监狱有连续编号为 的 个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱。
链接
题解
考虑计算「不会越狱的方案数」，用「方案总数」减去「不会越狱的方案数」即可。
方案总数：一共 个位置，每个位置有 种选择，总方案数为 。
不会越狱的方案数：第一个位置有 种选择，之后每个位置都不能与上一个位置相同，即有 种选择，方案数为 。
所以答案为 。
代码
#include <cstdio>
const long long MAXN = 1e12;
const long long MAXM = 1e8;
const long long MOD = 100003;
inline long long pow(const long long x, const long long n) {
long long ans = 1;
for (long long num = x % MOD, k = n; k; num = num * num % MOD, k >>= 1) if (k & 1) ans = ans * num % MOD;
// for (int i = 0; i < n; i++) ans = ans * x % MOD;
return ans;
}
int main() {
long long m, n;
scanf("%lld %lld", &m, &n);
long long ans = pow(m, n) - m * pow(m - 1, n - 1);
printf("%lld\n", (ans % MOD + MOD) % MOD);
return 0;
}