Description

小赛码举办了编程竞赛，所有参赛选手都到线下进行比赛。参赛选手有连续编号 $1$ 到 $n$，按编号顺序坐到一排，每个位置上只能坐一个人，不能坐别人身上！

这些参赛选手分别来自 $m$ 个班级，每名参赛选手只能来自其中某一个班级。

如果相邻座位的参赛选手来自同一个班级，就有可能作弊。

求有多少种状态可能会发生作弊的情况。

Format

Input

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

Output

可能发生作弊的状态数，对 $100003$ 取余。

Samples

2 3

6

4 3

28

样例提示

样例 $1$ 解释：所有可能的 $6$ 中状态：$(000)(001)(011)(100)(110)(111)$。