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. |