题目描述

有一个值域下标均为 $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$		$1$
$3 \sim 4$			$2$
$5 \sim 6$	$15$		$1$
$7 \sim 8$			$2$
$9 \sim 12$	$50$		$1$
$13 \sim 16$			$2$
$17$	$500$	$10$	$1$
$18$			$2$
$19$		$500$	$1$
$20$			$2$

对于所有数据，$1 \leq k < n \leq 500$，$1 \leq type \leq 2$。