题目描述

$n$ 名玩家使用一枚公平的 $k$ 面骰子（骰子各面编号为 $1$ 到 $k$，即每次投掷得到 $1$ 到 $k$ 中任意点数的概率均为 $\frac{1}{k}$）进行骰子游戏。初始时，每位玩家的得分均为零。

在单次行动中，得分最少的玩家投掷骰子，并将投掷结果加到自己的得分上。若在某一时刻有多名玩家并列得分最低，则由其中随机一名玩家行动。

当任意一名玩家累计得分达到 $m$ 分或以上时，游戏结束。求行动次数的期望值。

输入格式

输入的唯一一行包含三个整数 $n$、$k$、$m$（$1 \le n, k, m \le 10^6$），分别表示玩家人数、骰子面数以及获胜所需的分数。

输出格式

输出一个数，表示行动次数的期望值，对 $M = 10^9 + 7$ 取模后输出。

可以证明，答案可以表示为有理数 $p/q$ 的形式，其中 $p$ 和 $q$ 为整数，且 $q \ne 0 \pmod{M}$。请输出 $p \cdot q^{-1} \bmod M$ 的值。换句话说，输出满足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod{M}$ 的值 $x$。

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 4 \right) + \frac{1}{4} \cdot \left( \frac{3}{4} \cdot 4 + \frac{1}{4} \cdot 5 \right) \right) + \frac{1}{2} \cdot \left( \frac{3}{4} \cdot 3 + \frac{1}{4} \cdot 4 \right) + \frac{1}{4} \cdot 3 = \frac{461}{4^4}$$

由于 $256^{-1} = 285156252 \bmod M$，且 $461 \cdot 285156252 \equiv 457031255 \pmod{M}$，故答案为 $457031255$。