[AdditionalFile5683.zip](file://AdditionalFile5683.zip?type=additional_file)

#5683. 「PA 2026」Kostki

标签: 传统 | 时间限制: 2000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 PA 2026 Runda 3 Kostki

有 $n$ 名玩家使用一个有 $k$ 个面的公平骰子进行游戏，面上的数字编号为 $1$ 到 $k$（即掷骰子得到 $1$ 到 $k$ 中任意结果的概率均为 $\frac{1}{k}$）。初始时，每位玩家的分数为 $0$。

在每一轮中，当前分数最低的玩家掷骰子，并将掷出的结果加到自己的总分中。如果某一时刻有不止一名玩家的分数最低，则随机选择其中一名进行掷骰。

当有任何玩家积累了 $m$ 分或更多分数时，游戏结束。请计算游戏结束时的期望回合数。

输入格式

输入的第一行包含三个整数 $n, k, m$ $(1 \leq n, k, m \leq 10^{6})$，分别表示玩家人数、骰子的面数以及游戏结束所需达到的分数。

输出格式

输出一个整数，表示期望的回合数，对 $M=10^{9}+7$ 取模。

可以证明，答案可以表示为一个有理数 $p/q$，其中 $p$ 和 $q$ 是整数且 $q \not\equiv 0 \pmod M$。请输出 $p \cdot q^{-1} \pmod M$ 的值。换句话说，请输出一个满足 $x \cdot q \equiv p \pmod M$ 的整数 $x$ $(0 \leq x < M)$。

样例

输入

2 4 3

输出

457031255

我们有两名玩家，一个四面骰子，目标分数为 $3$ 分。在第一次掷骰子后，如果玩家掷出 $3$ 或 $4$（即概率为 $\frac{1}{2}$），游戏结束。如果没有结束，则第二名玩家进行第二次掷骰子。同样地，如果他掷出 $3$ 或 $4$（概率为 $\frac{1}{2}$），游戏结束。如果没有结束，那么有 $\frac{1}{4}$ 的概率两名玩家都得 $1$ 分（情况 A），$\frac{1}{2}$ 的概率其中一人得 $1$ 分另一人得 $2$ 分（情况 B），$\frac{1}{4}$ 的概率两名玩家都得 $2$ 分（情况 C）。

情况 A：第一名玩家掷骰子，有 $\frac{3}{4}$ 的概率在第三回合结束游戏。如果没有结束，第二名玩家掷骰子，有 $\frac{3}{4}$ 的概率在第四回合结束。如果没有结束，游戏一定在第五回合结束（由拥有 $2$ 分的玩家掷骰，他至少会再得 $1$ 分）。

情况 B：第一名玩家掷骰子，有 $\frac{3}{4}$ 的概率在第三回合结束，$\frac{1}{4}$ 的概率在第四回合结束。 情况 C：游戏一定在第三回合结束。 因此，总期望为：

$$\frac{1}{2} \cdot 1+\frac{1}{4} \cdot 2+\frac{1}{4} \cdot\left(\frac{1}{4} \cdot\left(\frac{3}{4} \cdot 3+\frac{1}{4} \cdot \frac{3}{4} \cdot 4+\frac{1}{4} \cdot \frac{1}{4} \cdot 5\right)+\frac{1}{2} \cdot\left(\frac{3}{4} \cdot 3+\frac{1}{4} \cdot 4\right)+\frac{1}{4} \cdot 3\right)=\frac{461}{4^{4}} .$$

因为 $256^{-1} \equiv 285156252 \pmod M$，且 $461 \cdot 285156252 \equiv 457031255 \pmod M$，所以答案为 $457031255$。