#1008. [HNOI2008]越狱

[HNOI2008]越狱

题目描述

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

答案对 105+310^5 + 3 取模。

输入格式

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

输出格式

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

2 3
6

样例说明

状态编号 一号房间 二号房间 三号房间
11 信仰 11 信仰 11 信仰 11
22 信仰 22
33 信仰 22
44 信仰 22 信仰 11
55 信仰 22 信仰 22
66 信仰 11

数据规模与约定

对于 100%100\% 的数据,保证 1m1081 \le m \le 10^81n10121 \le n \le 10^{12}