### Problem Statement

The skyline of the city of Terrapin City has N buildings all in a straight line; each building has a distinct height between 1 and N, inclusive. The building at index i is considered visible from the left is there is no building with a smaller index that is taller (formally, height[j] < height[i] for all j < i). Similarly, a building is visible from the right if there is no taller building with a higher index (height[j] < height[i] for all j > i). For example, if the buildings in order are {1, 3, 5, 2, 4}, then three buildings are visible from the left (1, 3 and 5), but only two are visible from the right (4 and 5).

You will be given N, leftSide and rightSide, corresponding to the total number of buildings, the buildings visible from the left, and the buildings visible from the right, respectively. Return the number of permutations of the buildings that are consistent with these values; as this can be a large number, you should return it modulo 1000000007.

### Definition

 Class: Skyscrapers Method: buildingCount Parameters: int, int, int Returns: int Method signature: int buildingCount(int N, int leftSide, int rightSide) (be sure your method is public)

### Constraints

-N will be between 1 and 100, inclusive.
-leftSide and rightSide will be between 1 and N, inclusive.

### Examples

0)

 `3` `2` `2`
`Returns: 2`
 There are two arrangements of buildings that match these requirements: {1, 3, 2} and {2, 3, 1}.
1)

 `3` `2` `1`
`Returns: 1`
 Only {2, 1, 3} fits these requirements.
2)

 `5` `3` `2`
`Returns: 18`
3)

 `12` `1` `1`
`Returns: 0`
 With 12 buildings, it is impossible for you to only see one building from each side.
4)

 `8` `3` `2`
`Returns: 4872`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8582

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=11129&pm=8582

connect4

#### Testers:

PabloGilberto , Olexiy , lovro , ivan_metelsky

#### Problem categories:

Dynamic Programming