H. Final Quiz
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Professor H is planning out a quiz for his subject. He wants to create $$$n$$$ multiple-choice questions, each with $$$k$$$ possible options.

At first, the professor desires to make a quiz such that all the problems have the same answer. However, the university has stated a regulation that all quizzes cannot contain any instance of four consecutive problems with the same answer. Formally, let $$$a_i$$$ be the answer of the $$$i$$$-th question in the quiz. For all $$$i$$$ from $$$1$$$ to $$$n-3$$$, if $$$a_i = a_{i+1} = a_{i+2}$$$, then $$$a_{i+3} \neq a_i$$$.

Still, the professor wants to follow his original idea. So instead, he aims to maximize the instances where three consecutive problems have the same answer.

You have been tasked to find out how many quizzes the professor can come up with. Two quizzes are different if there exists a problem that has different answer.

Input

The input consists of a single line containing integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 10^6$$$).

Output

Output the answer as an integer modulo $$$10^9 + 7$$$.

Examples
Input
5 2
Output
10
Input
2 4
Output
16
Note

In the first example, ten possible quizzes are $$$(1, 1, 1, 2, 1)$$$, $$$(1, 1, 1, 2, 2)$$$, $$$(1, 1, 2, 2, 2)$$$, $$$(1, 2, 1, 1, 1)$$$, $$$(1, 2, 2, 2, 1)$$$, $$$(2, 1, 1, 1, 2)$$$, $$$(2, 1, 2, 2, 2)$$$, $$$(2, 2, 1, 1, 1)$$$, $$$(2, 2, 2, 1, 1)$$$, and $$$(2, 2, 2, 1, 2)$$$.