Concatenation of two palindromes

Find the number of ways to construct a string of length $n$ using $k$ Latin letters (the size of the alphabet is $k$) as the concatenation of two nonempty palindromes.

Input

Two positive integers $n$ and $k(1\le n\le 10^5,1\le k\le 26)$.

Output

Print the number of ways to construct the given string. Print the answer modulo $10^9+7$.

Examples

In the first test case the string of length $4$ using one letter ($а$ for example) can be constructed in three ways: $a+aaa,aa+aa,aaa+a$.