StrangeColoring | Topcoder Archive

Problem Statement

M points are lying on a line and are colored with N different colors (numbered 1 to N) such that each point is coloured with exactly 1 color.

Two colorings c1 and c2 are considered âdifferentâ if and only if there exist a pair of points such that their color is same in c1 but different in c2 or they are different in c1 and same in c2. Otherwise they are considered âsimilarâ.

We define a set of different coloring as the set consisting of colorings of points such that no two elements in it are considered âsimilarâ.

What is the size of the largest set of different coloring mod 10⁹ + 7.

Definition

Class:: StrangeColoring
Method:: count
Parameters:: long, long
Returns:: int
Method signature:: int count(long n, long m)
(be sure your method is public)

Constraints

1 <= min(N, M) <= 106
1 <= max(N, M) <= 1018

Examples

```
2
```
```
2
```
```
Returns: 2
```
The different colorings possible are {1, 1}, {1, 2}, {2, 1} and {2, 2}. Among them {1, 1} and {2, 2} are similar and {1, 2} and {2, 1} are similar. So the largest set of different colorings is 2. For example, {{1, 1}, {1, 2}} contain no similar coloring.
```
10
```
```
15
```
```
Returns: 381367934
```

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.