#P9174. [COCI2022-2023#4] Bojanje

[COCI2022-2023#4] Bojanje

题目描述

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

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

输入格式

第一行包含三个整数 n,t,k (2kn10,1t1018)n,t,k\ (2\le k\le n\le 10,1\le t\le 10^{18}),意义如题目描述。

输出格式

输出一行一个数,表示答案对 109+710^9+7 取模后的值。

形式化地,令 m=109+7m=10^9+7。可以知道答案可以用不可约分数 pq\frac{p}{q} 表示,其中 ppqq 是整数,q≢0(modm)q\not\equiv 0 \pmod m。输出 pq1modmp\cdot q^{-1}\bmod m。换句话说,输出满足 0x<m0\le x<mxqp(modm)x\cdot q\equiv p\pmod m 的整数 xx

2 1 2
500000004
10 2 5
1
3 141592653589793 2
468261332

提示

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

样例 22 解释:在两次迭代后,不同的颜色数不可能从 1010 变为小于 55,所以在任何情况下这幅画都会有至少 55 种不同的颜色。

子任务编号 附加限制 分值
00 是样例 00
11 k=nk=n 2828
22 t1000t\le 1000 3636
33 无附加限制