#37 tree

Loading problem...

Preparing the statement, recent submissions, and submit form.

Authors: pk661

Time limit: 2000 ms
Memory limit: 1024 MB
Checker: CUSTOM
Solve threshold: 100

Statement

$1, 2, \cdots, N$ 번 정점으로 이루어진 루트가 있는 포레스트 중, 트리의 개수가 $K$ 개이고, 부모가 존재하며 서로 부모가 같은 두 정점의 집합 $\{u, v\}$ 의 개수가 $X$ 개인 것의 개수를 $10^9 + 7$ 로 나눈 나머지를 구하여라.

예를 들어 위 그림의 경우, $N = 10, K = 2, X = 5$ 이다.

Input

입력은 다음과 같은 형식으로 주어진다.

$N \ K \ X$

Output

첫째 줄에 정답을 출력한다.

Constraints

$2 \leq N \leq 100$ .
$1 \leq K \leq N$ .
$0 \leq X \leq \dfrac{N(N-1)}{2}$ .

Subtasks

#	Score	Constraints
1	1	$K = N$ .
2	28	$K = 1$ .
3	12	$X = 0$ .
4	25	$\displaystyle \sum_{i=1}^{N} A_i=N-K, \sum_{i=1}^{N} A_i^2=N-K+2X$ 를 만족하는 음이 아닌 정수 $A_1\le A_2\le \cdots \le A_N$ 이 유일하게 존재한다.
5	34	추가적인 제약조건이 없다.

Samples

Sample 1

Input

4 4 0

Output

이 예제는 서브태스크 1, 3, 4, 5의 조건을 만족한다.

Sample 2

Input

7 1 6

Output

3570

이 예제는 서브태스크 2, 5의 조건을 만족한다.

Sample 3

Input

5 2 0

Output

240

이 예제는 서브태스크 3, 4, 5의 조건을 만족한다.

Sample 4

Input

8 2 6

Output

39200

이 예제는 서브태스크 5의 조건을 만족한다.

Sample 5

Input

100 23 1379

Output

574317706

이 예제는 서브태스크 5의 조건을 만족한다.

Yet Another Tree Problem

Statement

Input

Output

Constraints

Subtasks

Samples