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
3
2
2
Returns: 2
There are two arrangements of buildings that match these requirements: {1, 3, 2} and {2, 3, 1}.
3
2
1
Returns: 1
Only {2, 1, 3} fits these requirements.
5
3
2
Returns: 18
100
2
1
Returns: 990953332
100
13
21
Returns: 492729563
12
1
1
Returns: 0
With 12 buildings, it is impossible for you to only see one building from each side.
8
3
2
Returns: 4872
15
2
1
Returns: 227020758
14
2
1
Returns: 479001600
12
11
3
Returns: 0
78
44
56
Returns: 0
87
23
11
Returns: 699722100
100
99
99
Returns: 0
100
95
4
Returns: 310413463
100
49
52
Returns: 504025591
67
32
24
Returns: 905017808
7
6
2
Returns: 6
9
5
5
Returns: 70
24
18
9
Returns: 0
1
1
1
Returns: 1
Minimum N.
2
2
1
Returns: 1
72
1
72
Returns: 1
87
87
1
Returns: 1
16
16
1
Returns: 1
37
1
37
Returns: 1
29
12
15
Returns: 269928514
77
6
10
Returns: 999993982
Maximal return value
73
11
2
Returns: 999991807
80
30
50
Returns: 999983834
95
40
54
Returns: 999954301
66
5
5
Returns: 999953844
100
8
7
Returns: 610390291
58
32
44
Returns: 0
87
5
13
Returns: 540283095
86
12
34
Returns: 810933864
78
54
22
Returns: 185138699
90
45
47
Returns: 0
90
45
46
Returns: 722170429
38
1
1
Returns: 0
87
1
1
Returns: 0
44
34
8
Returns: 956315439
71
55
8
Returns: 329451734
94
94
1
Returns: 1
87
1
87
Returns: 1
36
13
24
Returns: 834451800
12
3
1
Returns: 10628640
14
1
1
Returns: 0
9
9
2
Returns: 0
100
24
24
Returns: 520063872
100
40
41
Returns: 911646200
98
17
42
Returns: 393135880
100
20
23
Returns: 959802400
99
50
49
Returns: 528934656
100
25
25
Returns: 848175703
100
32
21
Returns: 790323138
100
100
1
Returns: 1
100
20
40
Returns: 667870492
100
2
2
Returns: 598881956
100
23
37
Returns: 714070384
100
39
29
Returns: 550026577
100
25
37
Returns: 702363931
100
25
61
Returns: 928920281
100
50
50
Returns: 265248055
100
53
37
Returns: 403760718
100
7
8
Returns: 610390291
100
35
35
Returns: 151954186
100
20
20
Returns: 986752476
100
49
50
Returns: 658420915
100
49
30
Returns: 175486704
100
20
29
Returns: 929804441
21
8
5
Returns: 651222009
100
50
51
Returns: 769496025
23
9
6
Returns: 384590516
99
7
7
Returns: 56353603
100
10
10
Returns: 559891373