Description

在外星语言中，有 $m$ 种字母。一个单词由若干个字母（可以有重复的字母）组成。

外星人认为回文是不吉利的，所以任意的单词都不会有长度大于 $1$ 且回文的后缀。

你需要计算出理论上存在多少个长度为 $n$ 个字母的单词。答案可能很大，输出其对质数 $10^9+7$ 取模的结果。

一个单词的后缀定义为将单词的前任意个（可以为零）字母删掉得到的字符串。例如 $\texttt{ab},\texttt{aacab},\texttt{acab}$ 是 $\texttt{aacab}$ 的后缀，但 $\texttt{acb},\texttt{aac},\texttt{bac}$ 不是。

一个字符串回文的定义为正着写和反着写相同。例如 $\texttt{level},\texttt{qwq},\texttt{acbbca}$ 回文，但 $\texttt{aabcc},\texttt{acbbac},\texttt{npodu}$ 不是。

Format

Input

两行，每行一个正整数。分别表示 $n,m\,(1\leq n\leq 3\times10^6,1\leq m\leq 10^9)$.

Output

仅一个非负整数表示答案。

Samples

2
8

56

5
3

78

10
26

625668701

Limitation

1s, 256MiB.