#P18852. [Croatian CPC2024] EA Enigma

[Croatian CPC2024] EA Enigma

EA Enigma

题目描述

Josip 正在玩一个猜词游戏。隐藏单词长度为 NN,每个位置的字符是 11 到 KK 中的一个整数。隐藏单词从所有 KNK^N 个可能的单词中等概率随机选出。

每次 Josip 可以提交一个长度为 NN 的猜测。游戏会告诉他每个位置上的字符是否猜对。当整个单词都被猜对时,游戏结束。游戏得分为提交猜测的次数。

如果 Josip 始终采取最优策略,求游戏得分的期望。

将答案表示为分数 p/qp/q,输出 p⋅q−1 mod (109+7)p\cdot q^{-1}\bmod(10^9+7)。

输入格式

一行包含两个整数 N,KN,K,满足 1≤N≤1061\le N\le10^6,1≤K≤1091\le K\le10^9。

输出格式

输出一个整数,表示所求期望对 109+710^9+7 取模的结果。

样例输入 1

4 8

样例输出 1

663085949

样例输入 2

8 8

样例输出 2

480783235

样例输入 3

3 2

样例输出 3

875000008

样例解释

第三个样例中,以 1/81/8 的概率第一次就全部猜对,否则第二次能猜对,期望为 1⋅18+2⋅78=1581\cdot\frac18+2\cdot\frac78=\frac{15}{8}。因此答案为 15⋅8−1 mod (109+7)=87500000815\cdot8^{-1}\bmod(10^9+7)=875000008。