问题描述

忙碌了一天的上官来到东京湾旁边的一家会员制餐厅吃饭。在仔细品尝菜品后，看向窗外时发现，好多青蛙都喜欢从河的一岸经过中间的石头跳到另一岸，于是他突发奇想，如果给青蛙加上骰子，青蛙根据每次摇出的数字来走会不会更刺激捏？

于是上官抓来了一只青蛙，名为德川。上官将他放在一个河宽为 $n - 1$ 的河的一岸，放的这一岸叫做 $a$，下标为 $0$，终点（即对岸）叫做 $b$，下标为 $n$，中间有 $n - 1$ 块石头，下标为 $1$ 到 $n - 1$。在河中，德川只能停在石头上，换句话说，德川的每步跳跃都是单位长度，例如从下标 $0$ 到 下标 $3$，德川需要这样： $0 - 1 - 2 - 3$，从 $0$ 跳三步到达 $3$。

但是上官觉得还差了点啥，于是又把骰子改造成了一个 $m$ 面的超级骰子，上面有 $1$ 到 $m$ 共 $m$ 个正整数，且每个面出现的概率相等。

德川一开始在 $a$ 岸（下标 $0$），朝着 $b$ 岸，每一次上官会掷骰子，根据骰子上的数字来决定德川向右跳的步数。

但是德川非常叛逆，如果某次掷出的跳跃步数 $x$ 加上此时德川所在的下标 $p$ 超过了 $b$ 岸，即 $x + p \gt n$，那么他会先到 $b$ 岸（下标 $n$ 处），而后再把剩下的步数 往回 跳完，最后仍然把朝向对着 $b$ 岸。

例如，假设 $n = 5$，德川当前在 $4$，如果骰子掷到了 $4$ 点，那他就会先从 $4$ 跳 一步到 $5$，再往回从 $5$ 跳三步到 $2$。若下一轮掷到 $2$ 点，则德川会从 $2$ 跳两步到 $4$，而不是继续向左跳。

可是这样掷下来也看不出啥，于是上官定了个规矩，只要德川恰好到达对岸 $b$（即跳完当前要走的所有步数后，恰好停在位置 $n$），那么上官就胜利了，游戏结束。

上官想让你求出掷骰子次数不超过 $k$ 次他能获胜的概率。

可以证明，答案是一个有理数，即

$$P= \frac{a}{b}，且 \space a \space 与 \space b \space 最大公约数为 \space 1$$

请输出 $P$ 模 $1000000007$ 的值，即输出 $a \times b^{-1}$ 模 $1000000007$ 的值，其中 $b^{-1}$ 为 $b$ 在模数意义下的乘法逆元。

输入输出格式

输入格式

一行三个正整数 $n$，$m$，$k$，分别表示石头总数，骰子面数，以及掷骰子的次数。

满足以下条件：

$$1 \leqslant m \leqslant n \leqslant 1000$$ $$1 \leqslant m \leqslant 10$$ $$1 \leqslant k \leqslant 1000$$

输出格式

一行一个整数，表示答案模 $1000000007$ 的值。

测试样例

8 1 9

1

10 5 6

774592006