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

0)

 `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.
1)

 `2` `2`
`Returns: 4`
2)

 `1` `1`
`Returns: 1`
 Here, there is only one staircase and one color to paint it.
3)

 `4` `5`
`Returns: 103514887`
4)

 `7` `77`
`Returns: 747707397`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10551

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13903&pm=10551

dzhulgakov

#### Testers:

PabloGilberto , ivan_metelsky , zhuzeyuan