409344: GYM103486 K Bracket Sequence

A balanced bracket sequence is a string consisting of only brackets ("$$$($$$" and "$$$)$$$").

One day, Carol asked Bella the number of balanced bracket sequences of length $$$2N$$$ ($$$N$$$ pairs of brackets). As a mental arithmetic master, she calculated the answer immediately. So Carol asked a harder problem: the number of balanced bracket sequences of length $$$2N$$$ ($$$N$$$ pairs of brackets) with $$$K$$$ types of bracket. Bella can't answer it immediately, please help her.

Formally you can define balanced bracket sequence with $$$K$$$ types of bracket with:

• $$$\epsilon$$$ (the empty string) is a balanced bracket sequence;
• If $$$A$$$ is a balanced bracket sequence, then so is $$$lAr$$$, where $$$l$$$ indicates the opening bracket and $$$r$$$ indicates the closing bracket. $$$lr$$$ must match with each other and forms one of the $$$K$$$ types of bracket.
• If $$$A$$$ and $$$B$$$ are balanced bracket sequences, then so is $$$AB$$$.

For example, if we have two types of bracket "$$$()$$$" and "$$$[]$$$", "$$$()[]$$$", "$$$[()]$$$" and "$$$([])$$$" are balanced bracket sequences, and "$$$[(])$$$" and "$$$([)]$$$" are not. Because "$$$(]$$$" and "$$$[)$$$" can't form can't match with each other.

A line contains two integers $$$N$$$ and $$$K$$$: indicating the number of pairs and the number of types.

It's guaranteed that $$$1 \le K, N \le 10^{5}$$$.

Output one line contains a integer: the number of balanced bracket sequences of length $$$2N$$$ ($$$N$$$ pairs of brackets) with $$$K$$$ types of bracket.

Because the answer may be too big, output it modulo $$$10^{9} + 7$$$.

1 2

2

2 2

8

24 20

35996330