{"problem":{"name":"[PA 2021] Od deski do deski","description":{"content":"给定 $n$，$m$，求满足以下限制的长度为 $n$ 的序列数目： 1. 每个元素在 $[1,m]$ 之间； 2. 一次操作定义为删除一个长度至少为 $2$ 且区间两端相等的区间，该序列需要在若干次操作内被删空。 答案对 $10^9+7$ 取模。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8386"},"statements":[{"statement_type":"Markdown","content":"给定 $n$，$m$，求满足以下限制的长度为 $n$ 的序列数目：\n\n1. 每个元素在 $[1,m]$ 之间；\n2. 一次操作定义为删除一个长度至少为 $2$ 且区间两端相等的区间，该序列需要在若干次操作内被删空。\n\n答案对 $10^9+7$ 取模。\n\n## Input\n\n第一行包含两个正整数 $n$，$m$。\n\n## Output\n\n输出一个整数，表示答案对 $10^9+7$ 取模后的结果。\n\n[samples]\n\n## Note\n\n### 样例解释\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$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8386","tags":["动态规划 DP","2021","PA（波兰）","DP 套 DP"],"sample_group":[["4 2","10"]],"created_at":"2026-03-03 11:09:25"}}