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.
The input consists of a single line containing integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 10^6$$$).
Output the answer as an integer modulo $$$10^9 + 7$$$.
5 2
10
2 4
16
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)$$$.
| Название |
|---|


