题目描述

一共有 $n$ 个盘子，$k$ 种菜，所有盘子排成一排，每个盘子只能放一种菜。要求最多连续两个盘子菜品一样，更长的重复出现是不允许的。

返回摆盘的方法数，答案可能很大，对 $10^9+7$ 取余。

输入格式

一行两个空格隔开的整数 $n$ 和 $k$，如题目描述所示。

输出格式

一行一个整数表示答案。

样例输入

2 1

样例输出

1

2 2

4

数据范围与提示

• $1 <= n <= 1000$
• $1 <= k <= 1000$