{"raw_statement":[{"iden":"statement","content":"给定 $n$，$m$，求满足以下限制的长度为 $n$ 的序列数目：\n\n1. 每个元素在 $[1,m]$ 之间；\n2. 一次操作定义为删除一个长度至少为 $2$ 且区间两端相等的区间，该序列需要在若干次操作内被删空。\n\n答案对 $10^9+7$ 取模。"},{"iden":"input","content":"第一行包含两个正整数 $n$，$m$。"},{"iden":"output","content":"输出一个整数，表示答案对 $10^9+7$ 取模后的结果。"},{"iden":"note","content":"### 样例解释\n\n合法序列有：\n\n$[1,1,1,1]$\n\n$[1,1,2,1]$\n\n$[1,1,2,2]$\n\n$[1,2,1,1]$\n\n$[1,2,2,1]$\n\n$[2,1,1,2]$\n\n$[2,1,2,2]$\n\n$[2,2,1,1]$\n\n$[2,2,1,2]$\n\n$[2,2,2,2]$\n\n### 数据范围\n\n$1 \\le n \\le 3000$，$1 \\le m \\le 10^9$。"}],"translated_statement":null,"sample_group":[["4 2","10"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}