[PA2021] Od deski do deski
题目描述
给定 $n$，$m$，求满足以下限制的长度为 $n$ 的序列数目：
1. 每个元素在 $[1,m]$ 之间；
2. 一次操作定义为删除一个长度至少为 $2$ 且区间两端相等的区间，该序列需要在若干次操作内被删空。
答案对 $10^9+7$ 取模。
输入输出格式
输入格式
第一行包含两个正整数 $n$，$m$。
输出格式
输出一个整数，表示答案对 $10^9+7$ 取模后的结果。
输入输出样例
输入样例 #1
4 2输出样例 #1
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$。