409344: GYM103486 K Bracket Sequence

Memory Limit:256 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

K. Bracket Sequencetime limit per test0.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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

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

ExamplesInput
1 2
Output
2
Input
2 2
Output
8
Input
24 20
Output
35996330

加入题单

上一题 下一题 算法标签: