1618：越狱

题目描述

监狱有连续编号为 $1$ 到 $n$ 的 $n$ 个房间，每个房间关押一个犯人。有 $m$ 种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人信仰的宗教相同，就可能发生越狱。求有多少种状态可能发生越狱。

输入格式

输入两个整数 $m$ 和 $n$。

输出格式

可能越狱的状态数，对 $100003$ 取余。

样例

样例输入 #1

2 3

样例输出 #1

6

样例解释 #1

• $m=2$ 种宗教（记为 $0$ 和 $1$），$n=3$ 个房间。
• 总状态数：$m^n = 2^3 = 8$ 种。
• 不可能越狱的状态（即任意相邻房间宗教不同）有 $m \times (m-1)^{n-1} = 2 \times 1^2 = 2$ 种（即 $010$ 和 $101$，但这里 $0$ 和 $1$ 表示宗教）。
• 可能越狱的状态数 = 总状态数 - 不可能越狱状态数 = $8 - 2 = 6$。
• 所有可能越狱的状态为：
  • $000$
  • $001$
  • $011$
  • $100$
  • $110$
  • $111$ （共 $6$ 种）

数据范围

对于全部数据：

• $1 \le m \le 10^8$
• $1 \le n \le 10^{12}$

时空限制

• 时间限制：1000 ms
• 内存限制：524288 KB

注意：本题用容斥原理（补集思想）求解。总方案数为 $m^n$（每个房间有 $m$ 种选择）。不可能越狱的方案数：第一个房间有 $m$ 种选择，之后每个房间都不能与前一房间相同，所以有 $m-1$ 种选择，因此不可能越狱的方案数为 $m \times (m-1)^{n-1}$。

可能越狱的方案数 = $m^n - m \times (m-1)^{n-1}$。

由于 $n$ 很大，需要用快速幂计算 $m^n \bmod 100003$ 和 $(m-1)^{n-1} \bmod 100003$。注意取模后可能出现负数，要加上模数再取模。

注意：当 $m=1$ 时，$m-1=0$，此时如果 $n=1$，则不可能越狱方案数为 $1 \times 0^0$，但 $0^0$ 未定义。实际上，$m=1$ 时只有一种宗教，任意相邻房间宗教相同，必然越狱，方案数为 $1^n - 1 \times 0^{n-1}$。当 $n=1$ 时，没有相邻房间，不会越狱，但根据定义，只有一个房间时不可能发生越狱（因为没有相邻房间），但题目可能认为单个房间不会越狱？实际上，题目要求“相邻房间的犯人信仰的宗教相同，就可能发生越狱”，如果只有一个房间，则没有相邻房间，所以不会越狱。但我们的公式：当 $m=1, n=1$ 时，总方案数 $1^1=1$，不可能越狱方案数 $1 \times 0^0$ 未定义。需要特殊处理：当 $m=1$ 时，不可能越狱方案数只有 $n=1$ 时为 $1$，$n>1$ 时为 $0$。但根据数据范围 $m \ge 1$，$n \ge 1$，我们直接计算 $m^n - m \times (m-1)^{n-1}$，并注意当 $m=1$ 且 $n=1$ 时，$(m-1)^{n-1} = 0^0$，在快速幂中需要处理 $0^0$ 为 $1$（或者特判）。实际上，在模意义下，$0^0$ 通常视为 $1$，但稳妥起见，特判 $m=1$ 的情况：此时可能越狱方案数为 $m^n - 1$（当 $n=1$）或 $m^n - 0$（当 $n>1$），即 $1 - 1 = 0$（$n=1$）或 $1 - 0 = 1$（$n>1$）。但根据定义，$m=1$ 时所有房间宗教相同，只要 $n>1$ 就会越狱，所以方案数为 $1$。对于 $n=1$，不会越狱，方案数为 $0$。所以最终公式仍然适用：$m^n - m \times (m-1)^{n-1}$，当 $m=1$ 时，$(m-1)^{n-1} = 0^{n-1}$，当 $n=1$ 时为 $0^0=1$，当 $n>1$ 时为 $0$。所以 $m \times (m-1)^{n-1} = 1 \times 1 = 1$（$n=1$）或 $1 \times 0 = 0$（$n>1$）。因此可能越狱方案数为 $1-1=0$（$n=1$）或 $1-0=1$（$n>1$），正确。所以直接使用公式即可，只需在快速幂中处理底数为 $0$ 且指数为 $0$ 的情况（返回 $1$）。