#1007. 比赛

比赛

Description

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

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

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

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

Format

Input

共一行,包含了两个整数 mmnn

Output

可能发生作弊的状态数,对 100003100003 取余。

Samples

2 3
6
4 3
28

样例提示

样例 11 解释:所有可能的 66 中状态:(000)(001)(011)(100)(110)(111)(000)(001)(011)(100)(110)(111)