Oliver 是一只橡皮鸭，它不仅能找出程序中的 bug，还喜欢绘画。它最新的画作有 $n$ 个部分，每个部分都涂有独特的颜色。在收到许多关于其画作过于单调的批评后，它决定在 $t$ 次迭代中修改这幅画。在每次迭代中，它会执行以下步骤：

1. Oliver 均匀随机地选择一个索引 $i$ ($1 \le i \le n$)，并记住画作中第 $i$ 部分的颜色。
2. 再次均匀随机地选择一个索引 $j$ ($1 \le j \le n$)。它将画作中第 $j$ 部分重新涂上第 $i$ 部分的颜色。如果第 $j$ 部分已经涂有该颜色，则画作保持不变。注意 $i$ 可以等于 $j$。

现在，Oliver 担心它的画作会变得单调乏味。如果画作上至少有 $k$ 种不同的颜色，它就认为这幅画是好的。请帮助它计算在 $t$ 次迭代结束时，画作是好的概率。

输入格式

第一行包含题目描述中的数字 $n$、$t$ 和 $k$ ($2 \le k \le n \le 10, 1 \le t \le 10^{18}$)。

输出格式

在唯一的一行中输出答案对 $10^9 + 7$ 取模的结果。

形式上，令 $m = 10^9 + 7$。可以证明答案可以表示为一个不可约分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 是整数且 $q \not\equiv 0 \pmod m$。输出等于 $p \cdot q^{-1} \pmod m$ 的整数。换句话说，输出一个满足 $0 \le x < m$ 且 $x \cdot q \equiv p \pmod m$ 的整数 $x$。

子任务

样例

输入格式 1

2 1 2

输出格式 1

500000004

说明

画作上有两种颜色，因此经过一次迭代后画作保持不变的概率为 $\frac{1}{2}$。

输入格式 2

10 2 5

输出格式 2

1

说明

经过两次迭代后，不同颜色的数量不可能从 10 减少到小于 5，因此在任何情况下，画作最终都会至少有 5 种不同的颜色。

输入格式 3

3 141592653589793 2

输出格式 3

468261332