Migrated from Lutece 1577 Joyful Palindr0me

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

A Palindrome string is a string which reads the same backward as forward, such as madam or racecar.

There is a problem about the palindrome string again.

We define the palindrome level of a string $S$ equals the number of the distinct palindrome substrings of $S$.

For example, "aa'' has the palindrome level $2$ and "aba'' has the palindrome level $3$.

Consider all the strings with the length $N$ and the charset size $M$, calculate the sum of their palindrome levels.

Input

Only one line contains two integers $N$ and $M$.

$1 \leq N \leq 100$, $1 \leq M \leq 10^9$.

Output

Print the corresponding answer modulo $10^9 + 7$.

Samples

3 2

24

2 3

18

Resources

The 15th UESTC Programming Contest Final