希蒙的摸鱼计划3
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
希蒙的摸鱼计划
题目描述
教室有 个位置，这些位置排成了一整行，其中有 种摸鱼方式，每个学生会按照一种方式摸鱼。但是如果相邻两个同学的摸鱼方式相同，就可能被老师发现，求有多少种状态会被老师发现。
答案对 取模。
输入格式
输入只有一行两个整数，分别代表摸鱼方式数 和学生数 。
输出格式
输出一行一个整数代表答案。
样例 #1
样例输入 #1
2 3
样例输出 #1
6
提示
样例输入输出 1 解释
| 状态编号 | 1 号位置 | 2 号位置 | 3 号位置 |
|---|---|---|---|
| 1 | 摸鱼 1 | 摸鱼 1 | 摸鱼 1 |
| 2 | 摸鱼 2 | ||
| 3 | 摸鱼 2 | ||
| 4 | 摸鱼 2 | 摸鱼 1 | |
| 5 | 摸鱼 2 | 摸鱼 2 | |
| 6 | 摸鱼 1 | ||
数据规模与约定
对于 的数据，保证 ，。