有连续放置的编号为1到n的n个盒子，每个盒子内有且仅有一个物品，不存在空盒子，总共有m种物品。

如果相邻盒子的物品是相同的，就会发生匹配。

求有多少种状态会发生匹配。

共一行，包含两个整数m和n。

数据范围：1≤m≤1e5， 1≤n≤1e7。

会发生匹配的状态数，对100003取余。