{"problem":{"name":"冒泡排序","description":{"content":"有一个值域下标均为 $1\\sim n$ 的排列或圆排列 $A$，定义 $f(A)$ 为将 $A$ 升序排序所需的最小操作次数。 每次操作中，你可以选择一个元素并向前**冒泡**若干次，一次**冒泡**定义为：若这个元素小于前一个元素，则可以交换它与前一个元素。当某次无法**冒泡**时，这次操作立即停止。否则可以连续**冒泡**任意次。 比如有排列 $[3,5,2,1,4]$，一次操作可以选择元","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":"LGP8859"},"statements":[{"statement_type":"Markdown","content":"有一个值域下标均为 $1\\sim n$ 的排列或圆排列 $A$，定义 $f(A)$ 为将 $A$ 升序排序所需的最小操作次数。\n\n每次操作中，你可以选择一个元素并向前**冒泡**若干次，一次**冒泡**定义为：若这个元素小于前一个元素，则可以交换它与前一个元素。当某次无法**冒泡**时，这次操作立即停止。否则可以连续**冒泡**任意次。\n\n比如有排列 $[3,5,2,1,4]$，一次操作可以选择元素 $1$ ，得到排列 $[3,5,1,2,4],[3,1,5,2,4]$ 或 $[1,3,5,2,4]$ 。\n\n若有圆排列 $[2,1,4,3]$，选择元素 $1$ 后可以得到圆排列 $[1,2,4,3],[3,2,4,1]$ 或 $[3,2,1,4]$ 。注意到圆排列中第 $1$ 个元素的前一个元素为第 $n$ 个元素。\n\n排列或圆排列被升序排序，当且仅当对于所有 $\\space 2 \\leq i \\leq n$，元素 $i$ 的前一个元素为元素 $i-1$。\n\n给定 $n,k,type$，你需要：\n- 在 $type=1$ 时求有多少长为 $n$ 的排列 $A$ 满足 $f(A)=k$ 。\n- 在 $type=2$ 时求有多少长为 $n$ 的圆排列 $A$ 满足 $f(A)=k$ 。\n\n答案对 $10^9+7$ 取模。\n\n## Input\n\n输入一行三个正整数 $n,k,type$，具体含义见题目描述。\n\n## Output\n\n输出一行一个整数，表示答案对 $10^9+7$ 取模后的结果。\n\n[samples]\n\n## Note\n\n#### 【样例解释 #1】\n\n有如下合法排列：\n\n1. $[1,4,2,3]$\n2. $[1,4,3,2]$\n3. $[2,1,4,3]$\n4. $[2,4,1,3]$\n5. $[2,4,3,1]$\n6. $[3,1,2,4]$\n7. $[3,1,4,2]$\n8. $[3,2,1,4]$\n9. $[3,2,4,1]$\n10. $[3,4,1,2]$\n11. $[3,4,2,1]$\n\n#### 【样例解释 #2】\n\n有如下合法圆排列：\n\n1. $[1,2,5,3,4]$\n2. $[1,2,5,4,3]$\n3. $[1,3,2,5,4]$\n4. $[1,3,5,2,4]$\n5. $[1,3,5,4,2]$\n6. $[1,4,2,3,5]$\n7. $[1,4,2,5,3]$\n8. $[1,4,3,2,5]$\n9. $[1,4,3,5,2]$\n10. $[1,4,5,3,2]$\n11. $[1,5,2,4,3]$\n12. $[1,5,3,2,4]$\n13. $[1,5,3,4,2]$\n14. $[1,5,4,2,3]$\n\n需要注意的是，我们认为 $[1,2,5,3,4]$ 和 $[2,5,3,4,1]$ 等是同一个圆排列。\n\n也就是我们认为两个圆排列不同，当且仅当存在一个 $2 \\leq i \\leq n$，满足两个圆排列中元素 $i$ 的前一个元素不同。\n\n#### 【数据范围】\n\n|   测试点编号 | $n \\leq$ | $k \\leq$ | $type=$ |\n|:------------:|:--------:|:--------:|:-------:|\n|  $1 \\sim 2$  |    $7$   |    $7$   |   $1$   |\n|  $3 \\sim 4$  |    $7$   |    $7$   |   $2$   |\n|  $5 \\sim 6$  |   $15$   |   $15$   |   $1$   |\n|  $7 \\sim 8$  |   $15$   |   $15$   |   $2$   |\n|  $9 \\sim 12$ |   $50$   |   $50$   |   $1$   |\n| $13 \\sim 16$ |   $50$   |   $50$   |   $2$   |\n|     $17$     |   $500$  |    $10$   |   $1$   |\n|     $18$     |   $500$  |    $10$   |   $2$   |\n|     $19$     |   $500$  |   $500$  |   $1$   |\n|     $20$     |   $500$  |   $500$  |   $2$   |\n\n对于所有数据，$1 \\leq k < n \\leq 500$，$1 \\leq type \\leq 2$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8859","tags":["动态规划 DP","贪心","洛谷原创","O2优化","组合数学","洛谷月赛"],"sample_group":[["4 2 1","11"],["5 2 2","14"],["50 10 1","808620624"],["50 10 2","578144115"]],"created_at":"2026-03-03 11:09:25"}}