题面描述

在你帮出题人打总力战的时候，出题人在看番。

憧憬会比剧毒更凶猛，比疾病更深切的猎杀着人们，一旦被其捕获，就在劫难逃，如同诅咒一般，但是冒险者们，依然义无反顾的为此献身，对他们来说失去憧憬的人生，比死亡更可怕。

所以憧憬 OI 的你决定做出这道题。

莉可在深渊底层寻找一个字符串 $S$ ，你找到一个数 $f(S)$ 与一头怪物。

记 $n$ 为 $S$ 的长度，$S[l,r]$ 为 $S_lS_{l+1}...S_{r-1}S_r$。

这头怪物告诉你，它已经将字符串 $S$ 变为了数 $f(S)$ ，具体等于 满足 $2\leq i\leq n,S[1,i]=S[n-i+1,n]$ 的 $i$ 的个数。

现在它告诉了你 $n$ 和 $S$ 的字符集大小 $k$ ，如果你能求出 $f^2(S)$ 的期望值对 $10^9+7$ 取模，它就会把 $f(S)$ 变回 $S$，否则它会跟莉可做一些羞羞的事情后生下一只可莉。

输入格式

一行两个整数 $n,k$。

输出格式

一行一个整数表示 $f^2(S)$ 的期望值。

数据范围

对于 $100\%$ 的数据，$1\leq n\leq10^7$，$1\leq k\leq10^9$。