冒泡排序

有一个值域下标均为 $1\sim n$ 的排列或圆排列 $A$，定义 $f(A)$ 为将 $A$ 升序排序所需的最小操作次数。 每次操作中，你可以选择一个元素并向前**冒泡**若干次，一次**冒泡**定义为：若这个元素小于前一个元素，则可以交换它与前一个元素。当某次无法**冒泡**时，这次操作立即停止。否则可以连续**冒泡**任意次。 比如有排列 $[3,5,2,1,4]$，一次操作可以选择元素 $1$ ，得到排列 $[3,5,1,2,4],[3,1,5,2,4]$ 或 $[1,3,5,2,4]$ 。 若有圆排列 $[2,1,4,3]$，选择元素 $1$ 后可以得到圆排列 $[1,2,4,3],[3,2,4,1]$ 或 $[3,2,1,4]$ 。注意到圆排列中第 $1$ 个元素的前一个元素为第 $n$ 个元素。 排列或圆排列被升序排序，当且仅当对于所有 $\space 2 \leq i \leq n$，元素 $i$ 的前一个元素为元素 $i-1$。 给定 $n,k,type$，你需要： - 在 $type=1$ 时求有多少长为 $n$ 的排列 $A$ 满足 $f(A)=k$ 。 - 在 $type=2$ 时求有多少长为 $n$ 的圆排列 $A$ 满足 $f(A)=k$ 。 答案对 $10^9+7$ 取模。

输入一行三个正整数 $n,k,type$，具体含义见题目描述。

输出一行一个整数，表示答案对 $10^9+7$ 取模后的结果。

4 2 1

11

5 2 2

14

50 10 1

808620624

50 10 2

578144115

#### 【样例解释 #1】 有如下合法排列： 1. $[1,4,2,3]$ 2. $[1,4,3,2]$ 3. $[2,1,4,3]$ 4. $[2,4,1,3]$ 5. $[2,4,3,1]$ 6. $[3,1,2,4]$ 7. $[3,1,4,2]$ 8. $[3,2,1,4]$ 9. $[3,2,4,1]$ 10. $[3,4,1,2]$ 11. $[3,4,2,1]$ #### 【样例解释 #2】 有如下合法圆排列： 1. $[1,2,5,3,4]$ 2. $[1,2,5,4,3]$ 3. $[1,3,2,5,4]$ 4. $[1,3,5,2,4]$ 5. $[1,3,5,4,2]$ 6. $[1,4,2,3,5]$ 7. $[1,4,2,5,3]$ 8. $[1,4,3,2,5]$ 9. $[1,4,3,5,2]$ 10. $[1,4,5,3,2]$ 11. $[1,5,2,4,3]$ 12. $[1,5,3,2,4]$ 13. $[1,5,3,4,2]$ 14. $[1,5,4,2,3]$ 需要注意的是，我们认为 $[1,2,5,3,4]$ 和 $[2,5,3,4,1]$ 等是同一个圆排列。 也就是我们认为两个圆排列不同，当且仅当存在一个 $2 \leq i \leq n$，满足两个圆排列中元素 $i$ 的前一个元素不同。 #### 【数据范围】 | 测试点编号 | $n \leq$ | $k \leq$ | $type=$ | |:------------:|:--------:|:--------:|:-------:| | $1 \sim 2$ | $7$ | $7$ | $1$ | | $3 \sim 4$ | $7$ | $7$ | $2$ | | $5 \sim 6$ | $15$ | $15$ | $1$ | | $7 \sim 8$ | $15$ | $15$ | $2$ | | $9 \sim 12$ | $50$ | $50$ | $1$ | | $13 \sim 16$ | $50$ | $50$ | $2$ | | $17$ | $500$ | $10$ | $1$ | | $18$ | $500$ | $10$ | $2$ | | $19$ | $500$ | $500$ | $1$ | | $20$ | $500$ | $500$ | $2$ | 对于所有数据，$1 \leq k < n \leq 500$，$1 \leq type \leq 2$。