题目描述

Oliver 是一只不仅能找出 bug 并且喜欢画画的小黄鸭。他最新的画有 $n$ 个部分，每部分用一种不同的颜色涂色。在此之后他得到了很多批评，因为他的画太可预测了。他决定用 $t$ 次迭代修改他的画。在每次迭代中他将做以下操作：

Oliver 会均匀随机选择一个下标 $i\ (1\le i\le n)$，然后记住画中第 $i$ 部分的颜色。 Oliver 会再均匀随机选择一个下标 $j\ (1\le j\le n)$。他会把画中第 $j$ 部分涂成和第 $i$ 部分一样的颜色。如果第 $j$ 部分的颜色和第 $i$ 部分相同，那么不会有任何改变。注意 $i$ 可以等于 $j$。 现在，Oliver 害怕他的画会变得十分单调或者无聊。他认为一幅画是好的，如果画上至少有 $k$ 种不同的颜色。请帮他计算最后这幅画是好的这个事件的概率。

输入格式

第一行包含三个整数 $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}\bmod m$。换句话说，输出满足 $0\le x<m$ 且 $x\cdot q\equiv p\pmod m$ 的整数 $x$。

2 1 2

500000004

10 2 5

1

3 141592653589793 2

468261332

提示

样例 $1$ 解释：画上有两种颜色，所以一次迭代后画和未操作之前相同的概率是 $\frac{1}{2}$。

样例 $2$ 解释：在两次迭代后，不同的颜色数不可能从 $10$ 变为小于 $5$，所以在任何情况下这幅画都会有至少 $5$ 种不同的颜色。