{"problem":{"name":"[AHOI2024 初中组 / 科大国创杯初中组 2024] 计数","description":{"content":"小可可做了一个梦，梦里从左到右有 $n$ 个糖果，每种糖果有一个颜色，用 $[1, m]$ 之间的一个正整数表示。 小可可每次会选择两个颜色相同的糖果，把它们以及它们之间的所有糖果吃掉。 小可可记得，对于梦里的糖果序列，存在一种方法把所有糖果吃完。 小可可醒来后忘记了梦中的糖果序列是什么，你能帮她求求在所有 $m^n$ 个可能的糖果序列中，有多少个糖果序列可能在小可可梦中（即存在一种全部吃完","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10375"},"statements":[{"statement_type":"Markdown","content":"小可可做了一个梦，梦里从左到右有 $n$ 个糖果，每种糖果有一个颜色，用 $[1, m]$ 之间的一个正整数表示。\n\n小可可每次会选择两个颜色相同的糖果，把它们以及它们之间的所有糖果吃掉。\n\n小可可记得，对于梦里的糖果序列，存在一种方法把所有糖果吃完。\n\n小可可醒来后忘记了梦中的糖果序列是什么，你能帮她求求在所有 $m^n$ 个可能的糖果序列中，有多少个糖果序列可能在小可可梦中（即存在一种全部吃完的方式）吗？\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## Background\n\n**本题的数据不是官方数据。**\n\n**本题征集（能够上传到这里的）官方数据。**\n\n**（没法上传到这里的）官方数据：<https://www.luogu.com.cn/training/499869>**\n\n**本题民间数据下载：<http://8.136.99.126/blog/3/67f0c2307aadac7b413b837b>**\n\n## Note\n\n### 样例 1 解释\n\n一共有 $4$ 个合法的糖果序列：$[1,1,1],[1,2,1],[2,1,2],[2,2,2]$。\n\n### 数据范围\n\n对于 $10\\%$ 的数据，$n \\le 6$，$m \\le 4$。\n\n对于 $20\\%$ 的数据，$n \\le 6$，$m \\le 100$。\n\n对于另外 $30\\%$ 的数据，$n \\le 50$，$m \\le 2$。\n\n对于 $70\\%$ 的数据，$n,m \\le 100$。\n\n对于 $80\\%$ 的数据，$n,m \\le 1000$。\n\n对于 $100\\%$ 的数据，$1 \\le n \\le 3000$，$1 \\le m \\le 10^9$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10375","tags":["动态规划 DP","2024","安徽","O2优化","DP 套 DP","科创活动","初中活动","科大国创杯"],"sample_group":[["3 2","4"],["6 3","405"],["30 2","73741759"],["100 100","566607183"]],"created_at":"2026-03-03 11:09:25"}}