Bajtazar 渴望亲近自然，摆脱城市的喧嚣，于是成为了 Bajtomil 森林里的一名伐木工人。他目前的任务是砍伐 $n$ 棵沿东西方向笔直排列的树。此外，他知道每棵树都属于 $m$ 种树木种类之一，但由于他刚开始从事伐木工作，偶尔会犯错，所以他不记得哪棵树属于哪种种类。

他决定每天从一棵尚未砍伐的树开始，然后向东走，砍伐沿途遇到的所有尚未砍伐的树。他必须在砍伐到与当天开始砍伐的树属于相同种类（但不一定是遇到的第一棵该种类的树）的树后立即结束当天的工作。他必须这样做，因为砍伐下来的树干将按砍伐顺序收集和打包，这样货物看起来才整洁美观。此外，他希望每天至少砍伐两棵树，以免给人留下偷懒的印象。

然而，他并非总能砍伐所有树木——这无疑取决于哪些树属于哪些种类。Bajtazar 想知道有多少种可能的树木种类序列，使得他（在任意天数后）能够砍伐所有树木。如果两个种类序列中至少有一棵树属于不同的种类，则认为它们是不同的。

请帮助他编写一个程序来计算这个数字。由于这个数字可能非常大，你只需输出它除以 $10^9 + 7$ 的余数。

输入格式

输入的第一行也是唯一一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 3000, 1 < m < 10^9$)。它们分别表示要砍伐的树木数量以及树木可能属于的种类数量。

输出格式

输出应包含一个整数，即可能的树木种类序列数量除以 $10^9 + 7$ 的余数。

样例

对于输入数据：

4 2

正确结果是：

10

样例解释：如果我们将种类标记为 1 和 2，那么 Bajtazar 能够成功完成工作的可能树木种类序列有：

• 1,1,1,1
• 1,1,2,1
• 1,1,2,2
• 1,2,1,1
• 1,2,2,1
• 2,1,1,2
• 2,1,2,2
• 2,2,1,1
• 2,2,1,2
• 2,2,2,2