题目描述

题目译自 PA 2021 Runda 1 Od deski do deski

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

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

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

输入格式

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

输出格式

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

4 2

10

数据范围与提示

$1 \leq n \leq 3000$, $1 \leq m \leq 10 ^ 9$