Background

JSOI has recently become interested in a new programming language called JS, and JYY wants to analyze some of its properties.

Description

The JS language is very simple. A JS program can be viewed as a string. It has no input and a single internal register, which is initially $0$ but can store any integer. It supports 5 different operations:

• Operation 1 "+": Increment the register by 1.
• Operation 2 "-": Decrement the register by 1.
• Operation 3 "!x": Call a library function. There are $K$ different library functions available depending on the version of the library, where $x$ is an integer between $1$ and $K$. This operation does not affect the current register value. Note that "!123" is a string of length 4.
• Operations 4 and 5 "[" and "]": Loops. In a valid program, "[" and "]" must be properly matched. When execution reaches "[", if the register is $0$, it jumps directly to the corresponding "]", otherwise it continues execution. When execution reaches "]", if the register is $0$, it continues execution, otherwise it jumps back to the corresponding "[".

A JS program is a string composed of the above operations. Except for loop operations, operations are executed in order from left to right.

After writing some programs, JYY discovered that some programs enter an infinite loop and never terminate, while others do not. Now, JYY wants to calculate how many JS programs of length $N$ do not enter an infinite loop, given $K$ library functions.

Input

The input contains two integers $N$ and $K$.

Output

Output a single integer representing the number of JS programs of length $N$ that do not enter an infinite loop when there are $K$ library functions, modulo $10^9+7$.

Examples

Input 1

3 1

Output 1

16

Note

In the first example, there is only one library function !1. The 16 programs that do not enter an infinite loop are: +++, -++, +-+, --+, []+, ++-, -+-, +--, ---, []-, [+], [-], !1+, !1-, +!1, -!1.

Input 2

5 9

Output 2

1010

Constraints

• For 30% of the data, $N \le 10$.
• For 50% of the data, $N \le 50$.
• For 100% of the data, $1 \le N \le 100$, $1 \le K < 10^4$.