#P18852. [Croatian CPC2024] EA Enigma
[Croatian CPC2024] EA Enigma
EA Enigma
题目描述
Josip 正在玩一个猜词游戏。隐藏单词长度为 ,每个位置的字符是 到 中的一个整数。隐藏单词从所有 个可能的单词中等概率随机选出。
每次 Josip 可以提交一个长度为 的猜测。游戏会告诉他每个位置上的字符是否猜对。当整个单词都被猜对时,游戏结束。游戏得分为提交猜测的次数。
如果 Josip 始终采取最优策略,求游戏得分的期望。
将答案表示为分数 ,输出 。
输入格式
一行包含两个整数 ,满足 ,。
输出格式
输出一个整数,表示所求期望对 取模的结果。
样例输入 1
4 8
样例输出 1
663085949
样例输入 2
8 8
样例输出 2
480783235
样例输入 3
3 2
样例输出 3
875000008
样例解释
第三个样例中,以 的概率第一次就全部猜对,否则第二次能猜对,期望为 。因此答案为 。