题目描述

给定 $n, m$，求满足以下限制的长度为 $n$ 的序列数目：

• 每个元素在 $[1, m]$ 之间；
• 一次操作定义为删除一个长度至少为 $2$ 且区间两端相等的区间，该序列需要在若干次操作内被删空。

答案对 $10^9 + 7$ 取模。

输入格式
第一行包含两个正整数 $n$，$m$。

输出格式
输出一个整数，表示答案对 $10^9 + 7$ 取模后的结果。

样例
输入

4 2

输出

10

合法序列有：
$[1, 1, 1, 1]$
$[1, 1, 2, 1]$
$[1, 2, 1, 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]$

数据范围与提示
$1 \leq n \leq 3000$
$1 \leq m \leq 10^9$