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.
|