P8386 [PA 2021] Od deski do deski
题目描述
给定 $n$，$m$，求满足以下限制的长度为 $n$ 的序列数目：
1. 每个元素在 $[1,m]$ 之间；
2. 一次操作定义为删除一个长度至少为 $2$ 且区间两端相等的区间，该序列需要在若干次操作内被删空。
答案对 $10^9+7$ 取模。
输入格式
无
输出格式
无
说明/提示
### 样例解释
合法序列有：
$[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$。