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 109 + 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
433786
372898436353436743
Returns: 352191334
46081666066812996
673079
Returns: 32046816
255274740500851546
817786
Returns: 867332592
505613973384492227
931341
Returns: 414765578
868932
769030060675163047
Returns: 601644806
406358
813360406590664559
Returns: 30936026
264416
570456203001954297
Returns: 649188582
750605975376552507
997085
Returns: 547925363
831244417453469410
64419
Returns: 864576820
990514698465592892
718600
Returns: 172976952
904008938614307244
739268
Returns: 235757127
92079
507523833765434682
Returns: 27807202
142322
164918911872431907
Returns: 537911159
30590694842996256
696553
Returns: 92055362
961437412048109867
209159
Returns: 239525688
118034
71677691296370304
Returns: 470201288
28321449067005805
39833
Returns: 320945659
652950488094763494
201237
Returns: 348102620