K. Bracket Sequence
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard 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$$$.

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