问题 D: 越狱
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：104
解决：50
题目描述
监狱有连续编号为1到n的n个房间，每个房间关押一个犯人。有m种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人信仰的宗教相同，就可能发生越狱。求有多少种状态可能发生越狱。
输入
输入两个整数m和n。
输出
可能越狱的状态数，对100003取余。
样例输入 复制
2 3样例输出 复制
6提示
所有可能的6种状态为：{0,0,0 }, {0,0,1 }, {0,1,1 }, {1,0,0 }, {1,1,0 }, {1,1,1 }。
对于全部数据，1≤m≤108,1≤n≤1012。
对于全部数据，1≤m≤108,1≤n≤1012。