Colored Brackets

Time limit2sMemory limit512 MB

Summary

Count valid bracket strings of 2N brackets over K colors that equal their own reversal, modulo 1e9+7.

Level: Hard9 of 10
Topics: Combinatorics, Math, Dynamic programming, Number theory
Solved: No attempts yet

Problem

A valid bracket string is defined by the following rules.

The empty string is a valid bracket string.
If $S$ is a valid bracket string, then $(S)$ is a valid bracket string. Putting an opening bracket in front of a valid bracket string and a closing bracket behind it keeps it valid.
If $S$ and $T$ are valid bracket strings, then $ST$ is a valid bracket string. Concatenating valid bracket strings keeps them valid.

Someone likes bracket strings very much. Using a single kind of bracket got dull, so he decided to paint the brackets with $K$ colors that can be told apart. An opening bracket of color $i$ pairs only with a closing bracket of color $i$ . For example, if $K = 3$ and the colors are red, green and blue, the second rule above grows into this.

If $S$ is a valid bracket string, then $(S)$ wrapped in red brackets, $(S)$ wrapped in green brackets and $(S)$ wrapped in blue brackets are all valid bracket strings. The opening bracket and the closing bracket of one pair always have the same color.

For a larger $K$ , add more distinguishable colors and extend the definition the same way.

Reversing a string means writing it down the way it looks in a mirror. The order of the characters is reversed, and each bracket becomes the bracket of the opposite direction in the same color. The colors stay where they are. With a single color, reversing (())() gives ()(()). That string differs from its reversal, so it must not be counted. ()(())() stays ()(())() after reversing, so it must be counted.

Count the valid bracket strings built from $2N$ brackets in $K$ colors that are equal to their own reversal.

Input

The first line contains two integers $N$ , the number that fixes how many brackets are used, and $K$ , the number of colors, separated by a space. ( $1 \le N \le 10^6$ , $1 \le K \le 10^6$ )

Output

Print how many valid bracket strings built from $2N$ brackets in $K$ colors are equal to their own reversal. This number can grow very large, so print it modulo 1,000,000,007.

Hint

For $N = 2$ and $K = 2$ there are 6 strings that satisfy the condition. Writing the two colors as 1 and 2 in subscripts, they are:

$(_1(_1)_1)_1$ , $(_1(_2)_2)_1$ , $(_2(_1)_1)_2$ , $(_2(_2)_2)_2$ , $(_1)_1(_1)_1$ , $(_2)_2(_2)_2$

The six cases

Examples5

Example 1
Input
```
2 2
```
Expected output
```
6
```
Example 2
Input
```
1 1
```
Expected output
```
1
```
Example 3
Input
```
2 1
```
Expected output
```
2
```
Example 4
Input
```
6 2
```
Expected output
```
408
```
Example 5
Input
```
10 5
```
Expected output
```
48412500
```