Competitions

# Simple Combinatorics

# 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** (**1** ≤ **n** ≤ `10`

, ^{5}**1** ≤ **k** ≤ **26**).

#### Output

Print the number of ways to construct the given string. Print the answer modulo `10`

+ ^{9}**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**.

Input example #1

4 1

Output example #1

3

Input example #2

3 2

Output example #2

8