We are given two strings A and B which satisfy these conditions :

1.A and B both consist of exactly n characters each.

2.Each character in A and B is one of the first k lowercase letters of English alphabet.

3.There exists a string C such that A+C=C+B.

Note: + denotes string concatenation

For example, if n = 3 and k = 4 then one valid pair of strings is ("aad", "daa"): both strings have length 3, only the first 4 letters are used in each of them, and C = "aa" shows that the third condition is satisfied as well.

We are given n and k. Find the number of such pairs of strings and return the number modulo 1,000,000,007.

Constraints

n<= 1000,000,000

k<=26