问题标题: 酷町堂：越狱

题目链接： 酷町堂：5299

5299   越狱

经验值：2400 时间限制：1000毫秒 内存限制：512MB

题目描述 Description

**有连续编号为 11 到 nn 的 nn 个房间，每个房间关押一个犯人。有 mm种**，每个犯人可能信仰其中一种。如果相邻房间的犯人信仰的**相同，就可能发生越狱。求有多少种状态可能发生越狱。

输入描述 Input Description

输入两个整数 mm 和 nn。

输出描述 Output Description

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

样例输入 Sample Input

2 3

样例输出 Sample Output

6

数据范围及提示 Data Size & Hint

样例说明

所有可能的 66
种状态为：{0,0,00,0,0} , {0,0,10,0,1} , {0,1,10,1,1} , {1,0,01,0,0} , {1,1,01,1,0} , {1,1,11,1,1}。

对于全部数据，1\le m\le 10^8,1\le n\le 10^{12}1≤m≤108,1≤n≤1012。