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.
Two positive integers n and k (1≤n≤105,1≤k≤26).
Print the number of ways to construct the given string. Print the answer modulo 109+7.
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.