越狱 ## 题目描述 监狱有连续编号为 $1,2 \cdots N$ 的 $N$ 个房间，每个房间关押一个犯人，有 $M$ 种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱。 ### 输入描述 输入两个整数 $M，N$。$1 \leq M \leq 10^8,1 \leq N \leq 10^{12}$。 ### 输出描述 输出可能越狱的状态数，结果模 $10^5+3$取余。 ### 输入输出样例 #### 示例 1 >输入 ```txt 2 3 ``` >输出 ```txt 6 ```