[HNOI2008] 越狱
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
监狱有 个房间,每个房间关押一个犯人,有 种宗教,每个犯人会信仰其中一种。如果相邻房间的犯人的宗教相同,就可能发生越狱,求有多少种状态可能发生越狱。
答案对 取模。
输入格式
输入只有一行两个整数,分别代表宗教数 和房间数 。
输出格式
输出一行一个整数代表答案。
2 3
6
提示
样例输入输出 1 解释
状态编号 | 1 号房间 | 2 号房间 | 3 号房间 |
---|---|---|---|
1 | 信仰 1 | 信仰 1 | 信仰 1 |
2 | 信仰 2 | ||
3 | 信仰 2 | ||
4 | 信仰 2 | 信仰 1 | |
5 | 信仰 2 | 信仰 2 | |
6 | 信仰 1 |
数据规模与约定
对于 的数据,保证 ,。