[HNOI2008]越狱

题目描述

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

输入输出格式

输入格式


输入两个整数 $M,N$

输出格式


可能越狱的状态数,模 $100003$ 取余

输入输出样例

输入样例 #1

2 3

输出样例 #1

6

说明

6种状态为(000)(001)(011)(100)(110)(111) $1 \le M \le 10^8$ $1 \le N \le 10^{12}$