$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 \not\equiv 0 \pmod M$。请输出 $p \cdot q^{-1} \pmod M$ 的值。换句话说，输出一个满足 $x \cdot q \equiv p \pmod M$ 的值 $x$ ($0 \le x < M$)。

样例

输入 1

2 4 3

输出 1

457031255

说明 1

我们有两名玩家、一枚四面骰子和 $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$。