e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Exponentiation

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) in the form of concatenation of two nonempty palindromes.

Input

Two positive integers n and k (1n105, 1k26).

Output

Print the number of ways to construct the given string. Print the answer modulo 109 + 7.

Explanation

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.

Time limit 1 second
Memory limit 128 MiB
Input example #1
4 1
Output example #1
3
Input example #2
3 2
Output example #2
8