题目背景

译自 Natjecanje timova studenata informatičara hrvatskih sveučilišta E.

题目描述

这是一道传统题。

交互库有一个隐藏的长度为 $n$，值域为 $[1,k]$ 的正整数序列 $a=[a_1,\ldots,a_n]$。

每次询问可以给定一个长度为 $n$，值域为 $[1,k]$ 的正整数序列 $[b_1,\ldots,b_n]$，交互库会告诉你猜对了哪些位置。也就是，交互库会返回一个长度为 $n$ 的 $01$ 序列 $s$，$s_i=1$ 表示 $a_i=b_i$，$s_i=0$ 表示 $a_i\neq b_i$。

交互库是非自适应的，也就是说序列 $a$ 已经事先确定。

对于序列 $[a_1,a_2,\ldots,a_n]$，定义 $f([a_1,a_2,\ldots,a_n])$ 为：如果交互库隐藏的序列为 $a=[a_1,a_2,\ldots,a_n]$，最优策略下要多少次才能猜出 $a$ 序列。

若交互库在 $k^n$ 个长度为 $n$，值域 $\in [1,k]$ 的正整数序列 $[a_1,a_2,\ldots,a_n]$ 中等概率独立随机选取一个，求出 $f$ 的期望值。

换句话说，令 $\displaystyle p=\sum_{1\le a_1\le k}\sum_{1\le a_2\le k}\cdots \sum_{1\le a_n\le k}f([a_1,a_2,\ldots,a_n])$，$q=k^n$，求出 $p/q$。

只需要输出答案对 $(10^9+7)$ 取模后的结果。

（注记：当且仅当交互库返回 $[1,1,\ldots,1]$ 时，认为猜出了序列。换句话说，就算已经事先确定这个序列，也要再询问一次。）

输入格式

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

输出格式

一行一个非负整数，表示答案对 $(10^9+7)$ 取模后的结果。

4 8

663085949

8 8

480783235

3 2

875000008

提示

样例解释

样例 $3$ 真实答案为 $\frac{1}{8}+\frac{7}{8}\cdot 2=\frac{15}{8}$。

数据范围

• $1\le n\le 10^6$；
• $1\le k\le 10^9$。