Description
监狱有 n 个房间，每个房间关押一个犯人，有 m 种宗教，每个犯人会信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱。
答案对 100,003 取模。
Input
输入只有一行两个整数，分别代表宗教数 m 和房间数 n。
HINT
对于 100% 的数据，保证 1≤m≤10^8，1≤n≤10^12。
样例输入输出 1 解释
|
状态编号
|
1 号房间
|
2 号房间
|
3 号房间
|
|
1
|
信仰 1
|
信仰 1
|
信仰 1
|
|
2
|
信仰 1
|
信仰 1
|
信仰 2
|
|
3
|
信仰 1
|
信仰 2
|
信仰 2
|
|
4
|
信仰 2
|
信仰 1
|
信仰 1
|
|
5
|
信仰 2
|
信仰 2
|
信仰 2
|
|
6
|
信仰 2
|
信仰 2
|
信仰 1
|