There is a string $S$, which is initially empty. A faulty decoder is continuously outputting characters and appending them to the end of $S$. In this problem, the size of the character set is $m$, and each time the decoder outputs a new character, it is chosen uniformly at random from the $m$ characters, each with a probability of $\frac{1}{m}$.

Because the decoder is faulty, after each character is output, it checks whether the current string $S$ is stable. The decoder considers the string $S$ to be unstable if and only if $S$ is a palindrome of length at least 2, or if it can be written in the form $S = U + U$ or $S = U + v + U$, where $U$ is any non-empty string and $v$ is any single character. For example, $abcabc$, $ababa$, and $abcab$ are all unstable, but any string of length 1 is stable. If the current string $S$ is unstable, the decoder resets $S$ to an empty string.

Write a program to calculate the expected number of characters the decoder must output to obtain a stable string $S$ of length exactly $n$, or determine if it is impossible. Note that even if the string is repeatedly reset during the process, the historical count of output characters is not cleared. For example, $a \to ab \to aba \to (\text{empty}) \to a \to ab \to abc$ results in a total of 6 characters output.

Input

The input contains one line with two positive integers $n, m$ ($1 \le n \le 12, 1 \le m \le 10^9$).

Output

Output a single integer representing the expected number of characters. If it is impossible to achieve, output -1. Otherwise, assuming the answer is $\frac{p}{q}$, you need to output the smallest non-negative integer $r$ such that $q \cdot r \equiv p \pmod{10^9 + 7}$. You may assume such an $r$ always exists.

Examples

Input 1

1 26

Output 1

1

Input 2

2 1

Output 2

-1

Input 3

2 2

Output 3

4

Input 4

6 26

Output 4

420983172