{"raw_statement":[{"iden":"statement","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$ 取模。"},{"iden":"input","content":"输入一行三个正整数 $n,k,type$，具体含义见题目描述。"},{"iden":"output","content":"输出一行一个整数，表示答案对 $10^9+7$ 取模后的结果。"},{"iden":"note","content":"#### 【样例解释 #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$。  "}],"translated_statement":null,"sample_group":[["4 2 1","11"],["5 2 2","14"],["50 10 1","808620624"],["50 10 2","578144115"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}