该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题面

医院里有连续编号为 1 到 $n$ 的 $n$ 个房间，每个房间都有一名病人。有 $m$种病毒，每个病人可能携带其中一种。如果相邻房间的病人携带的病毒一样，就可能发生超级感染。求有多少种状态可能发生超级感染。

输入格式

读入两个整数$m$和$n$。

输出格式

可能发生超级感染的状态数，对$100003$取余。

样例 #1

样例输入 #1

2 3

样例输出 #1

6

提示

样例说明： 所有可能的 $6$ 种状态为：$(000)(001)(011)(100)(110)(111)$。

对于$20$%的数据，$1 \leq n,m \leq 1000$

对于$100$%的数据，$1 \leq m \leq 10^8$, $1 \leq n \leq 10^{12}$。