Problem Statement
Time limit is 4 seconds.
Dunajec is a moderately wild river. Around the border between Slovakia and Poland, one popular tourist attraction is rafting on the river.
There are S sights along the river. The sights are in mutually distinct locations.
There are C different companies. Each company offers one raft excursion. Each excursion starts and ends somewhere along the river (at locations different from all the sights).
Each excursion takes the tourists along some non-empty contiguous segment of sights. Each sight can be seen from some non-empty subset of excursions (possibly all of them).
A schedule is a sequence in which we list, for each company, the set of sights visited by their excursion. Two schedules are considered distinct if there is some company that offers a different set of sights in each of them.
(All companies are distinguishable, so if two companies have different excursions and swap them, the new schedule is different from the previous schedule.)
Return the number of valid schedules, modulo 10^9 + 7.
Definition
- Class:
- RaftingOnDunajec
- Method:
- count
- Parameters:
- int, int
- Returns:
- int
- Method signature:
- int count(int S, int C)
- (be sure your method is public)
Constraints
- S will be between 1 and 100, inclusive.
- C will be between 1 and 100, inclusive.
Examples
7
1
Returns: 1
Seven sights, a single company. As each sight must be on some excursion, the only option is that the company offers an excursion along all the sights.
2
2
Returns: 7
Two sights, two companies. There are: one schedule such that both excursions contain both sights two schedules such that each excursion contains a different one of the two sights four schedules such that one company shows both sights and the other only one of the sights (In the last category we have two ways to choose the company with the longer excursion, and then two ways to choose which sight is shown during the shorter excursion.)
1
7
Returns: 1
As there is only one sight and each company must show some sight on its excursion, we again have just a single valid schedule.
100
100
Returns: 813449009
99
99
Returns: 632648885
99
100
Returns: 810699525
100
99
Returns: 100585642
2
20
Returns: 486784378
Remember to use the proper modular arithmetic when calculating the answer.
20
2
Returns: 799
100
1
Returns: 1
1
97
Returns: 1
6
2
Returns: 71
7
9
Returns: 901359530
8
10
Returns: 885444286
6
5
Returns: 2515861
9
7
Returns: 501835541
7
10
Returns: 363164608
1
7
Returns: 1
1
2
Returns: 1
1
5
Returns: 1
8
9
Returns: 524485112
1
6
Returns: 1
10
7
Returns: 603806418
4
4
Returns: 7183
9
9
Returns: 112124099
6
8
Returns: 515570431
4
1
Returns: 1
9
6
Returns: 133290453
6
10
Returns: 382839018
6
9
Returns: 137368856
10
4
Returns: 2188495
4
1
Returns: 1
3
6
Returns: 45137
2
6
Returns: 727
10
7
Returns: 603806418
9
9
Returns: 112124099
62
42
Returns: 37256699
59
72
Returns: 633162499
57
90
Returns: 258238189
44
83
Returns: 381284914
75
66
Returns: 34269684
60
63
Returns: 473585260
75
98
Returns: 236784983
35
91
Returns: 97937005
69
80
Returns: 443643022
63
96
Returns: 364216261
58
44
Returns: 591562002
56
78
Returns: 828524863
92
62
Returns: 554117251
49
86
Returns: 152885085
31
51
Returns: 221321784
100
40
Returns: 253621874
39
64
Returns: 112839840
95
99
Returns: 229138769
90
85
Returns: 691618568
76
34
Returns: 143141293
63
96
Returns: 364216261
90
70
Returns: 205488114
32
61
Returns: 309276387
57
74
Returns: 853301044
85
53
Returns: 316589750
50
100
Returns: 782985671
99
98
Returns: 554227560
89
97
Returns: 540800759