#1043. [HNOI2008] 越狱

[HNOI2008] 越狱

题目描述

监狱有 nn 个房间,每个房间关押一个犯人,有 mm 种宗教,每个犯人会信仰其中一种。如果相邻房间的犯人的宗教相同,就可能发生越狱,求有多少种状态可能发生越狱。

答案对 100,003100,003 取模。

输入格式

输入只有一行两个整数,分别代表宗教数 mm 和房间数 nn。

输出格式

输出一行一个整数代表答案。

样例

2 3
6

题目来源:洛谷 P3197