{"problem":{"name":"[COCI 2022/2023 #4] Bojanje","description":{"content":"Oliver 是一只不仅能找出 bug 并且喜欢画画的小黄鸭。他最新的画有 $n$ 个部分，每部分用一种不同的颜色涂色。在此之后他得到了很多批评，因为他的画太可预测了。他决定用 $t$ 次迭代修改他的画。在每次迭代中他将做以下操作： Oliver 会均匀随机选择一个下标 $i\\ (1\\le i\\le n)$，然后记住画中第 $i$ 部分的颜色。 Oliver 会再均匀随机选择一个下标 $j\\ (","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9174"},"statements":[{"statement_type":"Markdown","content":"Oliver 是一只不仅能找出 bug 并且喜欢画画的小黄鸭。他最新的画有 $n$ 个部分，每部分用一种不同的颜色涂色。在此之后他得到了很多批评，因为他的画太可预测了。他决定用 $t$ 次迭代修改他的画。在每次迭代中他将做以下操作：\n\nOliver 会均匀随机选择一个下标 $i\\ (1\\le i\\le n)$，然后记住画中第 $i$ 部分的颜色。\nOliver 会再均匀随机选择一个下标 $j\\ (1\\le j\\le n)$。他会把画中第 $j$ 部分涂成和第 $i$ 部分一样的颜色。如果第 $j$ 部分的颜色和第 $i$ 部分相同，那么不会有任何改变。注意 $i$ 可以等于 $j$。\n现在，Oliver 害怕他的画会变得十分单调或者无聊。他认为一幅画是好的，如果画上至少有 $k$ 种不同的颜色。请帮他计算最后这幅画是好的这个事件的概率。\n\n## Input\n\n第一行包含三个整数 $n,t,k\\ (2\\le k\\le n\\le 10,1\\le t\\le 10^{18})$，意义如题目描述。\n\n## Output\n\n输出一行一个数，表示答案对 $10^9+7$ 取模后的值。\n\n形式化地，令 $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$。\n\n[samples]\n\n## Note\n\n样例 $1$ 解释：画上有两种颜色，所以一次迭代后画和未操作之前相同的概率是 $\\frac{1}{2}$。\n\n样例 $2$ 解释：在两次迭代后，不同的颜色数不可能从 $10$ 变为小于 $5$，所以在任何情况下这幅画都会有至少 $5$ 种不同的颜色。\n \n| 子任务编号 | 附加限制 | 分值 |\n|:-:|:-:|:-:|\n| $0$ | 是样例 | $0$ |\n| $1$ |\t$k=n$ | $28$ |\n| $2$ |\t$t\\le 1000$ | $36$ |\n| $3$ |\t无附加限制 | $36$ |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9174","tags":["动态规划 DP","2022","矩阵加速","状态合并","COCI（克罗地亚）","状压 DP"],"sample_group":[["2 1 2","500000004"],["10 2 5","1"],["3 141592653589793 2","468261332"]],"created_at":"2026-03-03 11:09:25"}}