题目描述

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

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

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

输入格式

第一行包含两个正整数 $n$，$m$。

输出格式

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

4 2

10

提示

样例解释

合法序列有：

$[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]$

数据范围

$1 \le n \le 3000$，$1 \le m \le 10^9$。