题目描述
原题来自:HNOI 2008 监狱有连续编号为 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。