Migrated from Lutece 1850 MaxKU’s Z Algorithm

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

If you have ever learned $\underline{Z \, Algorithm}$, you may know that for a string $S$, $\underline{Z \, Algorithm}$ can gain an integer array $Z$, which $Z_i$ indicates the LCP(longest-common-prefix) between $S_{[i:n)}$ and $S_{[0:n)}$.

Besides, we explicitly define $Z_0 = 0$ as exception.

Now consider all the strings as set $\Re$ with the length $N$ and the charset size $M$, calculate $\sum_{S \in \Re} \max(Z_0,Z_1,...,Z_{n-1})^2 \mod 10^9 + 7$

Input

Only one line contains two integers $N$ $( 1 \leq N \leq 100 )$ and $M$ $( 1 \leq M \leq 666666666 )$.

Output

Print the corresponding answer in a single line.

Samples

1 772002

0

2 772002

772002

3 772002

975711675

Resources

The 16th UESTC Programming Contest Preliminary