题目描述

译自 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$。

样例 1

输入

2 1 2

输出

500000004

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

样例 2

输入

10 2 5

输出

1

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

样例 3

输入

3 141592653589793 2

输出

468261332

数据范围与提示

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

子任务编号	附加限制	分值
1	$k=n$	$28$
2	$t\le 1\,000$	$36$
3	无附加限制