Little H is a magician who owns a bracelet. This bracelet consists of $n$ beads, which are arranged in a circle. Initially, the reinforcement state of every bead is "unreinforced".

Little H now wants to reinforce this bracelet. Specifically, the reinforcement process is as follows:

1. Little H lays the bracelet flat on a table.
2. Little H selects a bead $c$ on the bracelet and decides to reinforce it.
3. Little H can choose any one of $k$ reinforcement methods to reinforce bead $c$. Let's assume Little H chooses the $i$-th reinforcement method ($1 \le i \le k$).
4. Regardless of the previous reinforcement state of bead $c$, after the reinforcement, its state becomes "$i$-reinforced".
5. At the same time, the reinforcement states of the two beads adjacent to $c$ become "unreinforced".

Little H can continue to reinforce this bracelet. The reinforcement can go on indefinitely, but Little H has discovered that the number of different bracelets that can be obtained this way is finite. Now, Little H wants to know how many different bracelets can be produced by using any number of reinforcements. Two bracelets are considered the same if and only if, after appropriately rotating one of them, the reinforcement states of the $n$ beads forming it are identical to the other. Please output the answer modulo $10^9 + 7$.

Input

A single line containing two integers $n$ and $k$.

Output

A single integer representing the number of possible configurations modulo $10^9 + 7$.

Examples

Input 1

4 10

Output 1

66

Input 2

1234 5678

Output 2

902765791

Subtasks

For all data, $n \ge 2$.