P11935 [CrCPC 2024] 萌萌交互题

译自 [Natjecanje timova studenata informatičara hrvatskih sveučilišta](https://hsin.hr/studenti2024/) 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)$ 取模后的结果。

#### 样例解释 样例 $3$ 真实答案为 $\frac{1}{8}+\frac{7}{8}\cdot 2=\frac{15}{8}$。 #### 数据范围 - $1\le n\le 10^6$； - $1\le k\le 10^9$。