3104. 越狱
时间限制：1000 MS 内存限制：64 MB
题目描述
## 题目描述 监狱有连续编号为 $1$ 到 $n$ 的 $n$ 个房间，每个房间关押一个犯人。 有 $m$ 种宗教，每个犯人可能信仰其中一种。 不存在没有信仰的犯人。 如果相邻房间的犯人信仰的宗教相同，就可能发生越狱。 求有多少种状态可能发生越狱。 ## 输入格式 共一行，包含两个整数 $m$ 和 $n$。 ## 输出格式 可能越狱的状态数，对 $100003$取余 ## 输入 ```in1 2 3 ``` ## 输出 ```out1 6 ``` ## 提示