RaftingOnDunajec | Topcoder Archive

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.
```
2
```
```
20
```
```
Returns: 486784378
```
Remember to use the proper modular arithmetic when calculating the answer.

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.