Inverse Descent Permutations

Time limit2sMemory limit128 MB

Summary

Count permutations of size N with a fixed first element F whose inverse permutation has exactly K descents.

Level: Medium7 of 10
Topics: Combinatorics, Dynamic programming, Math
Solved: No attempts yet

Problem

A permutation A = (A_0, A_1, ..., A_{N-1}) of length N contains each integer from 0 to N-1 exactly once. Let B = (B_0, B_1, ..., B_{N-1}) be the inverse permutation of A, so B_{A_i} = i. For example, if A = (2, 0, 3, 1, 4), then B = (1, 3, 0, 2, 4).

If the inverse permutation B has exactly K indices i such that B_i > B_{i+1}, call A a permutation with K inverse descents.

Given N, K, and F, count the permutations A such that A_0 = F and A has exactly K inverse descents.

Input

The first line contains N, the second line contains K, and the third line contains F.

Output

Print the number of permutations satisfying the condition.

Constraints

1 <= N <= 20
0 <= K <= N-1
0 <= F <= N-1

Examples4

Example 1
Input
```
7
3
2
```
Expected output
```
330
```
Example 2
Input
```
4
1
0
```
Expected output
```
4
```
Example 3
Input
```
2
1
0
```
Expected output
```
0
```
Example 4
Input
```
3
0
1
```
Expected output
```
0
```