Laine University is celebrating its fifteenth anniversary. This jubilation naturally ends with a fancy dinner for the whole University community consisting of 2n people. The restaurant offers m possible dishes and has a single long table that fits precisely n people in a row on both sides of the table. A catering is interesting if no two adjacent people have the same dish, where people are considered to be adjacent if they are in consecutive seats on a row or sit opposite to each other. How many interesting caterings are there?

Input

The only line of the input has two integers, n and m.

Output

Output a single integer, the number of interesting caterings modulo 10^9 + 7.

Constraints

• 1 \le n \le 10^6
• 1 \le m \le 10^9

Example

Input:

3 2

Output:

2

Explanation: There are two possible interesting caterings of dishes 1 and 2:

1 2 1
2 1 2

and

2 1 2
1 2 1