[HNOI2008]越狱

监狱有连续编号为 $1\sim n$ 的 $n$ 个房间，每个房间关押一个犯人。共有 $m$ 种宗教，每个犯人可能信仰其中一种。

如果相邻房间的犯人的宗教相同，就可能发生越狱。求有多少种状态可能发生越狱。

输入格式

输入一行两个整数 $m, n$，分别表示宗教数与房间数。

输出格式

输出一行一个整数，表示可能越狱的状态数对 $100003$ 取模的结果。

样例输入

2 3

样例输出

6

样例解释

可能越狱的 $6$ 种状态为：

$$(000)\quad(001)\quad(011)\quad(100)\quad(110)\quad(111).$$

数据范围

• $1\le m\le 10^8$；
• $1\le n\le 10^{12}$。

来源与许可

本题为 HNOI 2008 试题「越狱」，题面与测试数据整理自 BZOJ 1008。

样例 1

输入

2 3

输出

6