Problem Statement
A polar station consists of N sensors and two habitats for the researchers. The sensors measure various things: temperature, air pressure, the number of polar bears in vicinity, and so on. All N sensors are placed on the same circle around the habitats. The sensors are numbered from 0 to N-1 in the order in which they lie on the circle. For convenience, the habitats will get the numbers N and N+1.
Yesterday there were 2*N + 1 paths:
- N paths around the circle, each connecting one pair of cyclically adjacent sensors (i.e., one path connects sensors 0 and N-1 and each of the others connects sensors i and i+1 for some i)
- for each sensor a path from the sensor to exactly one of the habitats
- and finally, one path between the two habitats
Habitat N was connected to sensors with numbers between lo and hi, inclusive. Habitat N+1 was connected to all other sensors.
Last night, a blizzard covered all paths with fresh snow. The scientists at the station would like to be able to reach each other and all the sensors again. Thus, they need to pick up shovels and clean some of the paths. But, as you might expect, the scientists are not fond of manual labor and thus they are only willing to clean as few paths as possible (which is clearly always exactly N+1 paths).
Count the number of ways in which the scientists can shovel away the snow. Two ways are different if the sets of cleaned paths differ. Return the count modulo 10^9 + 7.
Definition
- Class:
- TwoPolarStations
- Method:
- count
- Parameters:
- int, int, int
- Returns:
- int
- Method signature:
- int count(int N, int lo, int hi)
- (be sure your method is public)
Notes
- You may only restore a subset of the original paths, you are not able to make new paths where there was no path before the snowfall.
Constraints
- N will be between 3 and 10^9, inclusive.
- 0 <= lo <= hi <= N-1.
Examples
3
0
2
Returns: 16
Sensors have numbers 0, 1, 2, habitats have numbers 3 and 4. As there is no other path from habitat 4, the scientists must clear the path between the two habitats. Then they have 16 options which three of the remaining paths they should clear. For example, they may clear the three paths from habitat 3 to the sensors. Another valid solution is to clear the paths 3-0, 0-1, and 0-2. Yet another valid solution is to clear the paths 3-0, 0-1, and 1-2. Cleaning the three paths between sensors does not work, as then you cannot get from the habitats to the sensors. Cleaning the paths 3-0, 3-1, and 0-1 does not work, as there is no way to reach sensor 2 from anywhere.
3
1
1
Returns: 24
Here habitat 3 was connected to sensor 1, while habitat 4 was connected to sensors 0 and 2.
10
1
4
Returns: 28325
4
0
3
Returns: 45
4
3
3
Returns: 69
14
1
6
Returns: 1344005
20
14
18
Returns: 431830245
13
4
8
Returns: 512143
15
6
9
Returns: 3489112
4
0
3
Returns: 45
6
0
2
Returns: 576
18
0
17
Returns: 33385280
13
6
9
Returns: 509017
10
3
8
Returns: 28325
19
11
14
Returns: 163916017
10
0
8
Returns: 23485
14
11
11
Returns: 1103479
14
5
9
Returns: 1340989
20
6
18
Returns: 433250895
10
0
2
Returns: 27885
13
1
5
Returns: 512143
15
8
8
Returns: 2888952
11
1
10
Returns: 61491
10
3
5
Returns: 27885
18
3
13
Returns: 63209808
14
10
13
Returns: 1332695
12
3
8
Returns: 195840
11
5
8
Returns: 74227
4
2
3
Returns: 75
15
4
11
Returns: 3521848
19
3
7
Returns: 164944407
9
6
7
Returns: 10184
11
8
9
Returns: 69849
7
0
3
Returns: 1537
8
1
1
Returns: 3423
255986
205084
210205
Returns: 988173468
7260999
278347
6368452
Returns: 787991392
410713460
326758089
345901504
Returns: 434259235
65217066
47525546
61365827
Returns: 993237449
875092130
23872914
619463997
Returns: 782411839
93239
45346
56575
Returns: 352963185
22173
6510
15394
Returns: 342397724
9804
2239
9332
Returns: 95587471
1871415
226670
559656
Returns: 230646818
8396189
2053125
6946942
Returns: 187955392
3560
84
1082
Returns: 450444341
1311
371
1047
Returns: 785066438
23526637
16599203
17725963
Returns: 132982515
8556167
1238920
2938064
Returns: 105443370
13735
764
10412
Returns: 851128722
394332362
32875367
382382525
Returns: 328278271
2613672
93172
371568
Returns: 65002890
290398
161305
287234
Returns: 905998057
85354
72080
75990
Returns: 85787207
152227
128779
147576
Returns: 937345407
579005
120161
433562
Returns: 653387551
7161712
2540173
4733866
Returns: 571211730
21463162
2131923
17041467
Returns: 20268872
7874
5348
6445
Returns: 645866030
8688547
1110509
7291091
Returns: 184388950
519151
59836
263399
Returns: 545208317
111698
43399
104366
Returns: 13639372
31541
740
19258
Returns: 916595734
7859
3772
7698
Returns: 450634518
137306
49620
75249
Returns: 148541743
999999999
99999999
588888888
Returns: 133210579