题目描述

译自 COCI 2022/2023 Contest #4 T3「Bojanje」

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

1. Oliver 会均匀随机选择一个下标 $i\ (1\le i\le n)$，然后记住画中第 $i$ 部分的颜色。
2. 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

数据范围与提示

详细子任务附加限制及分值如下表。