Cntnk

Bemfa has a new drawing board, which is split into $N$ rows, each row contains $N$ cells. He has $K$ different colors and now he is wondering in how many ways he can color the given board in such a way that each cell is colored with exactly one color and no two neighboring cells have the same color.

Two cells are considered to be neighbors if they share one side.

Help Bemfa count how many ways mod $10^9 + 7$ are there to color the board given the above mentioned constraints.

Input data

The first line of the input contains two integers, $N$ and $K$.

Output data

The output will contain a single integer, representing the answer to the given test case.

Constraints and Clarifications

• $1 \leq N \leq 8$;
• $2 \leq K \leq 5$;

Example 1

stdin

3 4

stdout

9612