题目描述

ch与yp终于要结婚了（人在泰国，刚下飞机）。他们两个邀请了各种亲朋好友来参加他们的婚礼，并且为每位客人分配了房间，房间编号 1 到 n 。在这些客人中有 m 种信仰，每个客人可能信仰其中一种。如果编号相邻房间的客人的信仰相同，就会发生争执。yp与ch喜欢看客人争执的样子，请问有多少种不同方案让客人们争执。

输入格式

输入两个整数 m 和 n。

输出格式

让客人们争执的方案数，对 100003 取余

样例

输入

2 3

输出

6

数据范围与提示

所有可能的 种状态为： {0,0,0},{0,0,1},{0,1,1},{1,0,0},{1,1,0},{1,1,1} 对于全部数据$1 \leq m \leq 10^8, 1 \leq n \leq 10^{12}$。