High-Rise Buildings

Time limit2sMemory limit128 MB

Summary

Count permutations of heights 1..N arranged so exactly L buildings are visible from the left and R from the right, modulo 1e9+7.

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

Problem

A neighborhood has N buildings in a row. All building heights are distinct, and each height is an integer from 1 to N.

When the row is viewed from one side, a building is visible only if it is taller than every building before it from that side. On the way to school, Sanggeun counted L visible buildings from the left. On the way home, he counted R visible buildings from the right.

Given N, L, and R, count how many height orders satisfy both visibility counts.

For instance, when N = 5, L = 3, and R = 2, 1 3 5 2 4 is one valid order.

Input

The first line contains three space-separated integers N, L, and R: the number of buildings, the number visible from the left, and the number visible from the right.

Output

Print the number of valid building orders modulo 1,000,000,007.

Constraints

1 <= N <= 100
1 <= L, R <= N

Examples5

Example 1
Input
```
3 2 2
```
Expected output
```
2
```
Example 2
Input
```
3 2 1
```
Expected output
```
1
```
Example 3
Input
```
5 3 2
```
Expected output
```
18
```
Example 4
Input
```
12 1 1
```
Expected output
```
0
```
Example 5
Input
```
8 3 2
```
Expected output
```
4872
```