P3197 [HNOI2008]越狱

admin

题目描述
监狱有连续编号为1…N 的 N个房间，每个房间关押一个犯人，有 M 种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱。

输入输出格式
输入格式：
输入两个整数 M，N

输出格式：
可能越狱的状态数，模 100003 取余

输入输出样例
输入样例#1：
2 3
输出样例#1：
6
说明
6种状态为(000)(001)(011)(100)(110)(111)

1≤M≤10^8
1≤N≤10^12