{"problem":{"name":"心跳","description":{"content":"赫尔德想对上面的问题进行探究，她想先做一些统计，于是她抽象了这个问题。 我们对于一个长为 $l$ 的数列 $p$，定义函数： -   $f(p)$ 表示有多少 $1\\le i\\le l$ 满足 $p_i=\\max_{j=1}^i p_j$（即前缀最大值的个数）。 现在，给定 $n,m$，请求出有多少满足以下条件的长为 $n$ 的，值域在 $[m,n]$ 数列 $a$： -   存在一个排列","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8554"},"statements":[{"statement_type":"Markdown","content":"赫尔德想对上面的问题进行探究，她想先做一些统计，于是她抽象了这个问题。\n\n我们对于一个长为 $l$ 的数列 $p$，定义函数：\n\n-   $f(p)$ 表示有多少 $1\\le i\\le l$ 满足 $p_i=\\max_{j=1}^i p_j$（即前缀最大值的个数）。\n\n现在，给定 $n,m$，请求出有多少满足以下条件的长为 $n$ 的，值域在 $[m,n]$ 数列 $a$：\n\n-   存在一个排列 $p$ 使得：令 $P_i$ 代表 $p$ 去掉 $p_i$ 后的数列（即 $[p_1,p_2,\\dots,p_{i-1},p_{i+1},\\dots,p_n]$），$f(P_i)=a_i$。\n\n答案对 $10^9+7$ 取模。\n\n## Input\n\n一行两个正整数表示 $n,m$。\n\n## Output\n\n一行一个数，表示答案。\n\n[samples]\n\n## Background\n\n“清晰的跳动声传达来的，重叠的声响和流动的思念。\n\n约定再也不要分开吧，希望无论何时都不要让你寂寞。”\n\n恋爱之时，人的心情不会一成不变，可喜悦和悲伤会随着时间流逝而归于平淡。最令人难忘的是那些“心动”的感觉，那些因未曾经历而喜出望外的感觉。因此，有些时候，失去某些特别美好的回忆，反而能让心动的感觉增多。可为此失去那些回忆，真的值得吗？\n\n## Note\n\n**【样例解释 \\#2】**\n\n有以下 $8$ 种不同的 $a$：\n\n1. $\\{4,4,4,4,4\\}$，对应的一种 $p$ 为：$\\{1,2,3,4,5\\}$；\n2. $\\{3,3,3,4,4\\}$，对应的一种 $p$ 为：$\\{1,2,3,5,4\\}$；\n3. $\\{3,3,4,4,3\\}$，对应的一种 $p$ 为：$\\{1,2,4,3,5\\}$；\n4. $\\{3,3,3,3,4\\}$，对应的一种 $p$ 为：$\\{1,2,4,5,3\\}$；\n5. $\\{3,4,4,3,3\\}$，对应的一种 $p$ 为：$\\{1,3,2,4,5\\}$；\n6. $\\{3,3,3,4,3\\}$，对应的一种 $p$ 为：$\\{1,3,4,2,5\\}$；\n7. $\\{4,4,3,3,3\\}$，对应的一种 $p$ 为：$\\{2,1,3,4,5\\}$；\n8. $\\{3,3,4,3,3\\}$，对应的一种 $p$ 为：$\\{2,3,1,4,5\\}$。\n\n---\n\n**【数据范围】**\n\n对于所有数据，保证 $3\\le n\\le 2000,1\\le m\\le n $。\n\n$$\n\\def\\arraystretch{1.5}\n\\begin{array}{c|c|c|c}\\hline \n\\textbf{子任务编号}&~~\\bm{n\\le} ~~&~~\\bm{m\\le}~~ &\\textbf{分数}\\cr\\hline \n\\textsf1 & 9 &1&8\\cr\\hline \n\\textsf2 & 18&1&12 \\cr\\hline \n\\textsf3 & 70&1&15\\cr\\hline \n\\textsf4 & 70 &&24\\cr\\hline \n\\textsf5 & 300&&18 \\cr\\hline\n\\textsf6 & &&23\\cr\\hline\\end{array}\n$$\n\n没写就是没特殊限制。\n\n---\n\n赫尔德成功算出了不同的恋爱的数量。但她只会经历其中一个。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8554","tags":["动态规划 DP","洛谷原创","O2优化","洛谷月赛"],"sample_group":[["3 1\n","6\n"],["5 3\n","8\n"],["50 10","664411387"]],"created_at":"2026-03-03 11:09:25"}}