Problem Statement
A very rich sultan built an enormous luxurious two-story palace containing several staircases. According to an old tradition, each staircase must:
- contain exactly N steps
- have a right angle in its base
- be built using exactly N rectangular blocks of arbitrary size
Staircases can be built using many different arrangements of blocks. For example, there are 5 ways to build a staircase with 3 steps:
To ensure that his palace is really the most luxurious in the world, the sultan decided to build one staircase for each possible arrangement of blocks.
The sultan is now preparing for a staircase coloring festival. He wants to paint each of the staircases in the palace in one of K different colors. Multiple staircases can be painted the same color, and it is not necessary to use all K colors. Help the sultan by calculating the total number of different ways he can color his staircases. The answer can be large, so return the count modulo 1000000123.
Definition
- Class:
- StairsColoring
- Method:
- coloringCount
- Parameters:
- int, int
- Returns:
- int
- Method signature:
- int coloringCount(int N, int K)
- (be sure your method is public)
Constraints
- N will be between 1 and 1000000000, inclusive.
- K will be between 1 and 1000000000, inclusive.
Examples
3
2
Returns: 32
As shown in the picture above, there are exactly 5 different ways to build a staircase with 3 steps. Each staircase can be painted in one of 2 different colors, for a total of 32 possible color combinations.
2
2
Returns: 4
1
1
Returns: 1
Here, there is only one staircase and one color to paint it.
4
5
Returns: 103514887
7
77
Returns: 747707397
1000000000
123
Returns: 1
1000000000
1000000000
Returns: 1
536870911
1000000000
Returns: 543724762
123456789
1
Returns: 1
268435455
36648724
Returns: 208048256
134217727
36648724
Returns: 1
117825866
7457346
Returns: 13498530
387420488
84069467
Returns: 806796213
643076642
123
Returns: 214970630
279
562444338
Returns: 47154375
11
358206529
Returns: 857359266
362
863193754
Returns: 274995007
120
438119233
Returns: 437630283
256
689481272
Returns: 90697485
8775
278000423
Returns: 572861679
2938
487044242
Returns: 410078719
7273
610019679
Returns: 711942185
3047
259939330
Returns: 832431563
8752
679078961
Returns: 618152009
959349
298165444
Returns: 373912105
271825
558967608
Returns: 728819731
604088
872931663
Returns: 755962687
754447
686456775
Returns: 372431019
848707
623629290
Returns: 224104687
930552
186804456
Returns: 237516386
197350
232952234
Returns: 974852665
798144
717319524
Returns: 887479123
840344
311701756
Returns: 356084284
712455
435488855
Returns: 747050769
280179047
138284830
Returns: 144167434
489152343
650268386
Returns: 807372474
131266783
482122404
Returns: 973886042
909833560
572746703
Returns: 377020583
214776896
461181366
Returns: 2124231
477365003
637517399
Returns: 705347008
439584539
933502299
Returns: 646156402
685949640
579379272
Returns: 414936531
319453138
683268749
Returns: 245072125
684365003
308843531
Returns: 43749586
999988776
2
Returns: 676672996
999999999
3
Returns: 1
999999997
4
Returns: 1
1000000000
5
Returns: 1
888888888
6
Returns: 1
999999997
999999997
Returns: 1
1000000000
500000000
Returns: 1
326402540
326402540
Returns: 113950251
987558789
987558789
Returns: 787202130
100028703
2
Returns: 133309173
46248482
7189719
Returns: 1
999998743
999998742
Returns: 345389292
423531123
8013
Returns: 223632865
11000
2645743
Returns: 798025601
100000000
599111111
Returns: 1
999999991
999999973
Returns: 1
24
2
Returns: 440011672
123
9999
Returns: 885229876
3627
2
Returns: 1
985575155
1337731
Returns: 1
131071
2
Returns: 596907532